結果
問題 |
No.1117 数列分割
|
ユーザー |
|
提出日時 | 2025-07-08 00:27:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 263 ms / 3,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 2,655 ms |
コンパイル使用メモリ | 206,572 KB |
実行使用メモリ | 73,728 KB |
最終ジャッジ日時 | 2025-07-08 00:27:20 |
合計ジャッジ時間 | 6,023 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<vector<long long>> dp(N + 1, vector<long long>(K + 1, INF)); dp[0][0] = 0; for (int k = 1; k <= K; k++) { deque<pair<long long, int>> dq_pos, dq_neg; for (int i = 1; i <= N; i++) { if (i - 1 >= 0 && dp[i - 1][k - 1] != INF) { long long val_pos = dp[i - 1][k - 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[i - 1][k - 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); } 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 (!dq_pos.empty()) dp[i][k] = max(dp[i][k], dq_pos.front().first - prefix[i]); if (!dq_neg.empty()) dp[i][k] = max(dp[i][k], dq_neg.front().first + prefix[i]); } } cout << dp[N][K] << '\n'; return 0; }