結果
問題 | No.3050 Prefix Removal |
ユーザー |
![]() |
提出日時 | 2025-03-07 21:43:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 288 ms / 2,000 ms |
コード長 | 1,748 bytes |
コンパイル時間 | 3,540 ms |
コンパイル使用メモリ | 278,908 KB |
実行使用メモリ | 16,604 KB |
最終ジャッジ日時 | 2025-03-07 21:43:26 |
合計ジャッジ時間 | 14,510 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long int K; template<class T> struct TopK { ll sum; priority_queue<T, vector<T>, greater<T>> ms; TopK() { sum = 0; } void insert(T x) { if ((int)ms.size() < K-1) { ms.push(x); sum += x; } else { if (ms.top() < x) { sum -= ms.top(); ms.pop(); sum += x; ms.push(x); } } } }; int main() { //dp[i][j] = i までで取り除いたpref = j //dp[i][j] = max(dp[i-1][k] + (S[j]-S[i])*i) (k < j) //dp[i][j] = max(dp[i-1][k]-S[k]*i + S[j]*i) //A[0]*1, A[1]*1, A[2]*2, A[2]*2 ... //A[0:] + A[2:] + A[x:] //dp[i][j] = i: で、すでにj個使ったときの場合の数 int N; cin >> N >> K; vector<ll> A(N); rep(i, 0, N) cin >> A[i]; if (K == 1) { ll now = 0; ll ans = -4e18; for (int i = 0; i < N; i++) { now += A[i]; ans = max(ans, now); } cout << ans << endl; return 0; } vector<ll> S(N+1); S[N] = 0; for (int i = N-1; i >= 0; i--) { S[i] = S[i+1] + A[i]; } ll ans = -4e18; TopK<ll> T; rep(i, 1, K) T.insert(S[i]); // for (auto v : S) cout << v << " "; // cout << endl; for (int last = K; last <= N; last++) { ll x = T.sum + S[0]; // cout << "last = "<< last << endl << x << " : " << S[last] << " : " << x - S[last]*K << endl; ans = max(ans, x - S[last] * K); if (last != N) { T.insert(S[last]); } } cout << ans << endl; }