結果
問題 |
No.2139 K Consecutive Sushi
|
ユーザー |
![]() |
提出日時 | 2022-12-07 09:07:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 247 ms / 2,000 ms |
コード長 | 1,156 bytes |
コンパイル時間 | 5,280 ms |
コンパイル使用メモリ | 311,100 KB |
実行使用メモリ | 14,848 KB |
最終ジャッジ日時 | 2024-11-27 19:53:08 |
合計ジャッジ時間 | 10,047 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
// #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; #define rep(i, n) for (int i=0; i<(int)(n); ++(i)) #define rep3(i, m, n) for (int i=(m); (i)<(int)(n); ++(i)) #define repr(i, n) for (int i=(int)(n)-1; (i)>=0; --(i)) #define rep3r(i, m, n) for (int i=(int)(n)-1; (i)>=(int)(m); --(i)) #define all(x) (x).begin(), (x).end() const ll LINF = (ll)(1e18); ll op(ll a, ll b) { return max(a, b); } ll e() { return -LINF; } ll mapping(ll f, ll x) { return x + f; } ll composition(ll f, ll g) { return f + g; } ll id() { return 0LL; } int main() { int n, k; cin >> n >> k; vector<int> a(n); rep(i, n) cin >> a[i]; vector<ll> sum(n+1); rep(i, n) sum[i+1] = sum[i] + a[i]; vector<ll> dp(n+1); lazy_segtree<ll, op, e, ll, mapping, composition, id> st(n+1); ll res = -LINF; dp[0] = 0; res = max(res, dp[0]); st.set(0, dp[0]); rep(i, n) { int li0 = max(0, (i+1)-(k-1)), li1 = max(0, (i+1)-k); dp[i+1] = st.prod(li1, i+1); res = max(res, st.prod(li0,i+1)+a[i]); st.apply(li0, i+1, a[i]); st.set(i+1, dp[i+1]); } res = max(res, dp[n]); cout << res << endl; return 0; }