Codeforces Round #343 (Div. 2) D. Babaei and Birthday Cake
問題設定ちょっと不自然な気がして最初誤読しました。普通上におけるのは体積の小さいものではなかろうか…?
解法
素直に dp 解法を取ろうとすると,
dp[i] = max(dp[j], j > i, vj > vi) + vi (vi は i の体積) となりますが, これを普通にやると O(n^2) かかります。
これを高速でやるために, まず体積 vi を座標圧縮しておきます(vi の座標圧縮した値を mp[vi] とします)。で, dp[i] を計算するには, [mp[vi]+1, ∞) の範囲の体積を持つものにおける dp の最大値を取っていけば良く, これは RMQ で O(log N) で計算できます。
// セグメント木(RMQ 対応) // update: k 番目の値を a に変更 // query: [l, r) の区間の最大値を求める template<typename T> struct ST { vector<T> seg; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(2*size-1, numeric_limits<T>::min()); } inline T merge(T x, T y) { return max(x, y); } void update(int k, T a) { k += size-1; seg[k] = a; while (k > 0) { k = (k-1)/2; seg[k] = merge(seg[k*2+1], seg[k*2+2]); } } T query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return numeric_limits<T>::min(); if (a <= l && r <= b) return seg[k]; T vl = query(a, b, k*2+1, l, (l+r)/2); T vr = query(a, b, k*2+2, (l+r)/2, r); return merge(vl, vr); } T query(int a, int b) { return query(a, b, 0, 0, size); } }; const int MAXN = 100100; ll R[MAXN], H[MAXN]; const double pi = acos(-1); ll dp[MAXN]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> R[i] >> H[i]; } map<ll, int> mp; for (int i = 0; i < n; i++) mp[R[i]*R[i]*H[i]] = 0; int size = 0; for (auto& p : mp) p.second = size++; ST<ll> seg(size); ll ans = 0; for (int i = n-1; i >= 0; i--) { ll v = R[i]*R[i]*H[i]; int index = mp[v]; ll tmp = max(0ll, seg.query(index+1, size)) + v; ans = max(ans, tmp); ll maxi = max(seg.query(index, index+1), tmp); seg.update(index, maxi); } printf("%.15lf\n", ans*pi); return 0; }