比赛 欢乐五一练练练 评测结果 AAAAAAAAAA
题目名称 疯狂动物城 最终得分 100
用户昵称 sxysxy 运行时间 0.257 s
代码语言 C++ 内存使用 4.87 MiB
提交时间 2017-04-26 22:30:46
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
const double PI = acos(-1);
const int MAXN = 1e5+10;
struct cake{
  int R, H, id, th;
  bool operator<(const cake &ck)const{
    return R < ck.R;
  }
  double calc(){
    return PI*R*R*H;
  }
}cs[MAXN], csq[MAXN];
bool cmp(cake x, cake y){
  return x.id < y.id;
}
double f[MAXN];
double c[MAXN];
int H;
double query(int p){
  double ans = 0;
  for(int i = p; i <= H; i += i&-i)ans = max(ans, c[i]);
  return ans;
}
double update(int p, double v){
  for(int i = p; i; i -= i&-i)c[i] = max(c[i], v);
}
int main(){
 // freopen("test_data.out", "r", stdin);
  freopen("zootopia.in", "r", stdin);
  freopen("zootopia.out", "w", stdout);
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    scanf("%d %d", &cs[i].R, &cs[i].H);
    cs[i].id = i;
  }
  sort(cs+1, cs+1+n);
  cs[1].th = H = 1;
  for(int i = 2; i <= n; i++)cs[i].th = H = H+(cs[i].R != cs[i-1].R);
  sort(cs+1, cs+1+n, cmp);
  double ans = 0;
  for(int i = 1; i <= n; i++){
    f[i] = query(cs[i].th+1)+cs[i].calc();
    update(cs[i].th, f[i]);
    ans = max(ans, f[i]);
  }
  printf("%.2lf\n", ans);
  return 0;
}