比赛 |
欢乐五一练练练 |
评测结果 |
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;
}