結果
問題 |
No.1117 数列分割
|
ユーザー |
|
提出日時 | 2025-07-08 00:21:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 141 ms / 3,000 ms |
コード長 | 1,605 bytes |
コンパイル時間 | 2,508 ms |
コンパイル使用メモリ | 204,776 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-07-08 00:21:53 |
合計ジャッジ時間 | 4,914 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long INF = -1e18; int main() { int N, K, M; cin >> N >> K >> M; vector<long long> A(N + 1), prefix(N + 1); for (int i = 1; i <= N; i++) { cin >> A[i]; prefix[i] = prefix[i - 1] + A[i]; } vector<long long> dp_prev(N + 1, INF); dp_prev[0] = 0; for (int k = 1; k <= K; k++) { vector<long long> dp_curr(N + 1, INF); deque<pair<long long, int>> dq_pos, dq_neg; for (int i = 1; i <= N; i++) { while (!dq_pos.empty() && dq_pos.front().second < i - M) dq_pos.pop_front(); while (!dq_neg.empty() && dq_neg.front().second < i - M) dq_neg.pop_front(); if (i - 1 >= 0) { long long val_pos = dp_prev[i - 1] + prefix[i - 1]; while (!dq_pos.empty() && dq_pos.back().first <= val_pos) dq_pos.pop_back(); dq_pos.emplace_back(val_pos, i - 1); long long val_neg = dp_prev[i - 1] - prefix[i - 1]; while (!dq_neg.empty() && dq_neg.back().first <= val_neg) dq_neg.pop_back(); dq_neg.emplace_back(val_neg, i - 1); } if (!dq_pos.empty()) dp_curr[i] = max(dp_curr[i], dq_pos.front().first - prefix[i]); if (!dq_neg.empty()) dp_curr[i] = max(dp_curr[i], dq_neg.front().first + prefix[i]); } dp_prev = dp_curr; } cout << dp_prev[N] << endl; return 0; }