mayoko’s diary

プロコンとかいろいろ。

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;
}