比赛 ZLXSCDay2 评测结果 AAAAAAAAAA
题目名称 疯狂动物城 最终得分 100
用户昵称 葳棠殇 运行时间 0.233 s
代码语言 C++ 内存使用 1.89 MiB
提交时间 2016-04-10 17:52:15
显示代码纯文本
#include <cstdio>
#include <algorithm>
using namespace std;
#define Pi 3.1415926535897932384626433832795
int R[100005],H[100005];
double V[100005],C[10005];
void Update(int pos,double val){
	while(pos<=10000){
		C[pos]=max(C[pos],val);
		pos+=pos&(-pos);
	}
}
double Query(int pos){
	double ans=0;
	while(pos){
		ans=max(ans,C[pos]);
		pos-=pos&(-pos);
	}
	return ans;
}
double ans,f;
int n;
int main(){
	freopen("zootopia.in","r",stdin);freopen("zootopia.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&R[i],&H[i]),V[i]=Pi*R[i]*R[i]*H[i];
	for(int i=n;i;i--){
		f=Query(R[i]-1)+V[i];
		Update(R[i],f);
		ans=max(ans,f);
	}
	printf("%.2lf\n",ans);
	return 0;
}