結果
問題 |
No.1117 数列分割
|
ユーザー |
|
提出日時 | 2020-07-18 02:58:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 340 ms / 3,000 ms |
コード長 | 2,583 bytes |
コンパイル時間 | 1,865 ms |
コンパイル使用メモリ | 176,316 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 19:37:13 |
合計ジャッジ時間 | 6,044 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr char newl = '\n'; constexpr ll INF = 1e17; // [Related]: semigroup // https://scrapbox.io/data-structures/Sliding_Window_Aggregation template<class SemiGroup> struct SWAG { using T = typename SemiGroup::T; struct Node { T val, sum; Node(const T& v, const T& s) : val(v), sum(s) {} }; stack<Node> front_stack, back_stack; SWAG() {} bool empty() const { return front_stack.empty() && back_stack.empty(); } size_t size() const { return front_stack.size() + back_stack.size(); } T fold_all() { assert(!empty()); if (front_stack.empty()) return back_stack.top().sum; else if (back_stack.empty()) return front_stack.top().sum; else return SemiGroup::merge(front_stack.top().sum, back_stack.top().sum); } void push(const T& x) { if (back_stack.empty()) { back_stack.emplace(x, x); } else { T sum = SemiGroup::merge(back_stack.top().sum, x); back_stack.emplace(x, sum); } } void pop() { assert(!empty()); if (front_stack.empty()) { front_stack.emplace(back_stack.top().val, back_stack.top().val); back_stack.pop(); while (!back_stack.empty()) { T sum = SemiGroup::merge(front_stack.top().sum, back_stack.top().val); front_stack.emplace(back_stack.top().val, sum); back_stack.pop(); } } front_stack.pop(); } }; template <class U = ll> struct RSQSG { using T = U; static T merge(const T& a, const T& b) { return max(a, b); } }; ll solve(int n, int K, int m, const vector<ll>& sum) { vector<ll> dp(n + 1, -INF); dp[0] = 0; for (int i = 0; i < K; i++) { vector<ll> ndp(n + 1, -INF); SWAG< RSQSG<> > sw, sw2; for (int j = 0; j < n; j++) { sw.push(dp[j] - sum[j]); if (sw.size() > m) sw.pop(); sw2.push(dp[j] + sum[j]); if (sw2.size() > m) sw2.pop(); ndp[j + 1] = max(sw.fold_all() + sum[j + 1], sw2.fold_all() - sum[j + 1]); } dp = move(ndp); } return dp[n]; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, K, m; cin >> n >> K >> m; vector<ll> sum(n + 1, 0); for (int i = 0; i < n; i++) { cin >> sum[i + 1]; sum[i + 1] += sum[i]; } cout << solve(n, K, m, sum) << newl; return 0; }