记录编号	248689	评测结果	AAAAAAAAAA
题目名称	疯狂动物城	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	1.297 s
提交时间	2016-04-10 20:33:08	内存使用	8.87 MiB

#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <iomanip>
#define N 100020
using namespace std;
typedef long double ld;
int n;
ld V[N],f[N],R[N];
int S[N]={0};
ld pi=3.1415926535898;
ifstream cin("zootopia.in");
ofstream cout("zootopia.out");
class rangetree
{
public:
	ld maxv[3*N];
	void clear(int size){memset(maxv,0,sizeof(maxv));}
	void update(int o,int l,int r,int x,ld v)
	{
		if(l==r)maxv[o]=v;
		else
		{
			int mid=(l+r)>>1;
			if(x<=mid)update(o<<1,l,mid,x,v);
			else update(o<<1|1,mid+1,r,x,v);
			maxv[o]=fmax(maxv[o<<1],maxv[o<<1|1]);
		}
	}
	ld query(int o,int l,int r,int ql,int qr)
	{
		int mid=(l+r)>>1;
		if(ql<=l&&r<=qr)return maxv[o];
		ld ans=0;
		if(ql<=mid)ans=fmax(ans,query(o<<1,l,mid,ql,qr));
		if(mid<qr)ans=fmax(ans,query(o<<1|1,mid+1,r,ql,qr));
		return ans;
	}
}A;
void print(ld x,int y){cout <<setprecision(y) <<std::fixed <<x<<endl;}
map<ld,int > F;
ld C[N],D[N];
bool com(ld a,ld b){return a>b;}
void lisanhua()//对R[i]离散化
{
	int i,m=0;
	for(i=1;i<=n;i++)C[i]=R[i];
	sort(C+1,C+n+1,com);
	for(i=1;i<n;i++)if(C[i]==C[i+1])C[i]=-1;
	for(i=1;i<=n;i++)if(C[i]!=-1)D[++m]=C[i];
	//for(i=1;i<=m;i++)cout<<D[i]<<' ';
	//cout<<endl;
	for(i=1;i<=m;i++)F[D[i]]=i;
	for(i=1;i<=n;i++)S[i]=F[R[i]]+1;
}
void read()
{
	int i;
	ld H;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>R[i]>>H;
		V[i]=R[i]*R[i]*H*pi;
	}
}
void work()
{
	int i;
	ld ans=0,temp;
	A.clear(n+1);
	memset(f,0,sizeof(f));
	/*for(i=1;i<=n;i++)cout<<V[i]<<' ';
	cout<<endl;*/
	/*for(i=1;i<=n;i++)cout<<S[i]<<' ';
	cout<<endl;*/
	/*int j;
	R[0]=9999999;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<i;j++)
		{
			if(R[j]>R[i])f[i]=max(f[i],f[j]+V[i]);
		}
	}*/
	for(i=1;i<=n;i++)
	{
		temp=A.query(1,1,n+1,1,S[i]-1);
		f[i]=temp+V[i];
		temp=A.query(1,1,n+1,S[i],S[i]);
		if(f[i]>temp)A.update(1,1,n+1,S[i],f[i]);
	}
	for(i=1;i<=n;i++)ans=fmax(ans,f[i]);
	print(ans,2);
}
int main()
{
	read();
	lisanhua();
	work();
	return 0;
}