比赛 ZLXSCDay2 评测结果 AAAAAAAAAA
题目名称 疯狂动物城 最终得分 100
用户昵称 Zayin 运行时间 0.342 s
代码语言 C++ 内存使用 2.08 MiB
提交时间 2016-04-10 15:23:02
显示代码纯文本
#include<cstdio> 
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define maxn 100050
using namespace std;
typedef long long LL;

int n;
double V[maxn];
int R[maxn],H[maxn];
double tree[maxn];
const double pi=acos(-1);

void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	{
		scanf("%d%d",&R[i],&H[i]);
		V[i]=R[i]*R[i]*pi*H[i];
	}
}
int lowbit(int x)
{
	return x&(-x);
}
double query(int i)
{
	double ans=0;
	for (;i;i-=lowbit(i))
		ans=max(ans,tree[i]);
	return ans;
}
void change(int i,double d)
{
	for (;i<maxn;i+=lowbit(i))
		tree[i]=max(tree[i],d);
}
void solve()
{
	double ans=0;
//	cout<<pi<<endl;
	for (int i=n;i;--i)
	{
//		cout<<i<<endl;
		double v=query(R[i]-1)+V[i];
		change(R[i],v);
		ans=max(ans,v);
	}
	printf("%.2lf\n",ans);
}
int main()
{
	freopen("zootopia.in","r",stdin);
	freopen("zootopia.out","w",stdout);
	init();
	solve();
	return 0;
}