记录编号	405438	评测结果	AAAAAAAAAA
题目名称	疯狂动物城	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.144 s
提交时间	2017-05-16 20:13:19	内存使用	2.60 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

#ifndef LOCAL
const int MAXN = 1e5 + 10;
#else
const int MAXN = 1e3 + 10;
#endif
const double PI = 3.1415926535897932384626433832795028841971;

inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp)) tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct DATA{
	LL r, v;

	DATA(int b, int a){
		r = a, v = a * a * b;
	}
	DATA(){
		r = 0, v = 0;
	}
};

struct NODE{
	LL val;
	NODE *ls, *rs;

	NODE(){
		ls = rs = NULL;
	}
};

NODE* build(int l, int r);
LL query(NODE *now, int l, int r, int L, int R);
void update(NODE *now, int k, int L, int R);

int N;
LL f[MAXN], maxr, ans;
DATA cake[MAXN];
NODE *root;

int main(){ 
#ifndef LOCAL
	freopen("zootopia.in", "r", stdin);
	freopen("zootopia.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	N = in();

	for(int i = 1; i <= N; ++i){ 
		cake[i] = DATA(in(), in());
		maxr = max(maxr, cake[i].r);
	}

	root = build(1, maxr);

	for(int i = 1; i <= N; ++i){
		if(cake[i].r == maxr) f[i] = cake[i].v;
		else f[i] = query(root, cake[i].r + 1, maxr, 1, maxr) + cake[i].v;

		update(root, i, 1, maxr);
	}

	for(int i = 1; i <= N; ++i) ans = max(ans, f[i]);

	printf("%.2lf", ans * PI);

	return 0;
}

NODE* build(int l, int r){ 
	NODE *p = new NODE();

	if(l != r){ 
		int mid = (l + r) >> 1;
		p->ls = build(l, mid);
		p->rs = build(mid + 1, r);
	}

	return p;
}

LL query(NODE *now, int l, int r, int L, int R){ 
	if(l == L && r == R) return now->val;

	int mid = (L + R) >> 1;
	if(r <= mid) return query(now->ls, l, r, L, mid);
	if(mid < l) return query(now->rs, l, r, mid + 1, R);

	return max(query(now->ls, l, mid, L, mid), query(now->rs, mid + 1, r, mid + 1, R));
}

void update(NODE *now, int k, int l, int r){
	if(l == r){ 
		now->val = max(now->val, f[k]);
		return ;
	}

	int mid = (l + r) >> 1;
	if(cake[k].r <= mid) update(now->ls, k, l, mid);
	else update(now->rs, k, mid + 1, r);

	now->val = max(now->ls->val, now->rs->val);
	return ;
}