結果

問題 No.3050 Prefix Removal
ユーザー SnowBeenDiding
提出日時 2025-03-07 22:13:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 144 ms / 2,000 ms
コード長 2,833 bytes
コンパイル時間 6,534 ms
コンパイル使用メモリ 333,144 KB
実行使用メモリ 17,896 KB
最終ジャッジ日時 2025-03-07 22:14:03
合計ジャッジ時間 13,316 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

template <typename T, typename Compare = less<T>,
          typename RCompare = greater<T>>
struct PrioritySumStructure {
    int k;
    T sum;

    priority_queue<T, vector<T>, Compare> in, d_in;
    priority_queue<T, vector<T>, RCompare> out, d_out;

    PrioritySumStructure(int k) : k(k), sum(0) {}

    void modify() {
        while (in.size() - d_in.size() < k && !out.empty()) {
            auto p = out.top();
            out.pop();
            if (!d_out.empty() && p == d_out.top()) {
                d_out.pop();
            } else {
                sum += p;
                in.emplace(p);
            }
        }
        while (in.size() - d_in.size() > k) {
            auto p = in.top();
            in.pop();
            if (!d_in.empty() && p == d_in.top()) {
                d_in.pop();
            } else {
                sum -= p;
                out.emplace(p);
            }
        }
        while (!d_in.empty() && in.top() == d_in.top()) {
            in.pop();
            d_in.pop();
        }
    }

    T query() const { return sum; }

    void insert(T x) {
        in.emplace(x);
        sum += x;
        modify();
    }

    void erase(T x) {
        assert(size());
        if (!in.empty() && in.top() == x) {
            sum -= x;
            in.pop();
        } else if (!in.empty() && RCompare()(in.top(), x)) {
            sum -= x;
            d_in.emplace(x);
        } else {
            d_out.emplace(x);
        }
        modify();
    }

    void set_k(int kk) {
        k = kk;
        modify();
    }

    void inc_k() { set_k(k + 1); }

    void dec_k() { set_k(k - 1); }

    int get_k() const { return k; }

    int size() const {
        return in.size() + out.size() - d_in.size() - d_out.size();
    }
};

template <typename T>
using MaximumSum = PrioritySumStructure<T, greater<T>, less<T>>;

template <typename T>
using MinimumSum = PrioritySumStructure<T, less<T>, greater<T>>;

ll solve(int n, int k, vector<ll> a) {
    ll bas = 0, smk = 0;
    rep(i, 0, k) smk += a[i];
    MaximumSum<ll> max_sum(k);
    rep(i, 0, k) {
        if (i == 0) {
            max_sum.insert(smk + (ll)1e16);
        } else {
            max_sum.insert(smk);
        }
        smk -= a[i];
    }
    ll ans = max_sum.query() - (ll)1e16;
    rep(i, k, n) {
        bas += a[i];
        max_sum.insert(a[i] - bas);
        ll val = max_sum.query() + bas * k - (ll)1e16;
        ans = max(ans, val);
    }
    return ans;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i];
    cout << solve(n, k, a) << endl;
}
0