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

# include <bits/stdc++.h>
# define MAXN 100023
# define Pi (3.1415926535897932384626433832795028841971)
# define mid ((l + r) >> 1)
using namespace std;
inline int gn() {
	int k = 0;
	char c = getchar();
	for(; !isdigit(c); c = getchar());
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k;
}
struct node {
	long long mx;
	node *ls, *rs;
	inline node() {
		ls = rs = NULL;
		mx = 0;
	}
}*root;
struct cake {
	int r, h;
	long long dp;
}ck[MAXN];
int n;
node *build(int l, int r) {
	node *x = new node();
	if(l == r) {
		x->mx = 0;
		return x;
	} else {
		x->ls = build(l, mid);
		x->rs = build(mid + 1, r);
		x->mx = 0;
		return x;
	}
}
void change(node *x, int l, int r, cake *k) {
	if(l == r) {
	  x->mx = max(k->dp, x->mx);
		return;
	} else {
		if(k->r <= mid) change(x->ls, l, mid, k);
		else change(x->rs, mid + 1, r, k);
		x->mx = max(x->ls->mx, x->rs->mx);
	}
}
double query(node *x, int l, int r, int s, int t) {
	if(s > t) return 0;
	if(l == s && r == t) return x->mx;
	else if(mid >= t) return query(x->ls , l, mid, s, t);
	else if(mid < s) return query(x->rs, mid + 1, r, s, t);
	else return max(query(x->ls, l, mid, s, mid), query(x->rs, mid + 1, r, mid + 1, t));
} 
int maxr;
long long ans;
int main() {
	freopen("zootopia.in", "r", stdin);
	freopen("zootopia.out", "w", stdout);
	n = gn();
	for(int i = 1; i <= n; i++) {
		cake *c = ck + i;
		c->r = gn();
		c->h = gn();
		maxr = max(maxr, c->r);
		c->dp = c->r * c->r * c->h;
	}
	//for(int i = 1; i <= n; i++) printf("%d ", ck[i].dp);
	puts("\n");
	root = build(1, maxr);
	change(root, 1, maxr, ck + 1);
	for(int i = 2; i <= n; i++) {
		cake *c = ck + i;
		c->dp += query(root, 1, maxr, c->r + 1, maxr);
		change(root, 1, maxr, c);
		ans = max(ans, c->dp);
	}
	//for(int i = 1; i <= n; i++) printf("%d ", ck[i].dp);
	printf("%.2lf", ans * Pi);
}