记录编号	401678	评测结果	AAAAAAAAAA
题目名称	疯狂动物城	最终得分	100
用户昵称	zChengYuan	是否通过	通过
代码语言	C++	运行时间	0.285 s
提交时间	2017-05-03 17:15:32	内存使用	1.84 MiB

#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
//ifstream fin("zootopia.in");
//ofstream fout("zootopia.out");
const double pi=3.1415926535897932384626433832795028841971;
double V[100010];
int n;
struct cake
{
	int r,h;
	double v(){return r*r*pi*h;}
};
cake a[100010];
inline int lowbit(int x){return x&-x;}
void update(int x,double v)
{
	for(int i=x;i<=100010;i+=lowbit(i))
		V[i]=max(V[i],v);
}
double findmax(int x)
{
	double ans=0;
	for(int i=x;i>0;i-=lowbit(i))
		ans=max(ans,V[i]);
	return ans;
}
int main()
{
	freopen("zootopia.in","r",stdin);
	freopen("zootopia.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i].r>>a[i].h;
	double ans=0;
	for(int i=n;i>0;--i)
	{
		double v=findmax(a[i].r-1)+a[i].v();
		update(a[i].r,v);
		ans=max(ans,v);
	}
	printf("%.2lf\n",ans);
}