結果

問題 No.3050 Prefix Removal
ユーザー rin204
提出日時 2025-02-03 21:54:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 196 ms / 2,000 ms
コード長 966 bytes
コンパイル時間 12,161 ms
コンパイル使用メモリ 356,060 KB
実行使用メモリ 40,036 KB
最終ジャッジ日時 2025-03-07 20:32:42
合計ジャッジ時間 20,929 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include "testlib.h"

void solve() {
    int n = inf.readInt(1, 500000);
    inf.readSpace();
    int k = inf.readInt(1, n);
    inf.readEoln();
    std::vector<int> A = inf.readInts(n, -10'000'000, 10'000'000);
    inf.readEoln();

    long long ans = 0;
    for (int i = 0; i < k; i++) {
        ans += (long long)A[i] * (i + 1);
    }
    long long tot   = 0;
    long long l_tot = 0;
    std::priority_queue<long long> pq;
    for (auto a : A) {
        tot += a;
        if (int(pq.size()) >= k - 1) {
            long long score = tot * k - l_tot;
            if (score > ans) ans = score;
        }

        l_tot += tot;
        pq.push(tot);
        if (int(pq.size()) == k) {
            l_tot -= pq.top();
            pq.pop();
        }
    }

    std::cout << ans << std::endl;
}

int main(int argc, char *argv[]) {
    std::cin.tie(0)->sync_with_stdio(0);
    registerValidation(argc, argv);
    solve();
    inf.readEof();
}
0