結果
問題 | No.2139 K Consecutive Sushi |
ユーザー |
👑 |
提出日時 | 2022-12-03 00:07:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 1,824 ms |
コンパイル使用メモリ | 200,064 KB |
最終ジャッジ日時 | 2025-02-09 04:32:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include<atcoder/lazysegtree> using namespace std; using namespace atcoder; using ll = long long; const ll inf = 1LL << 60; using S = ll; S op(S l, S r){ return max(l, r); } S e(){ return -inf; } using F = ll; S mapping(F f, S x){ return f + x; } F composition(F l, F r){ return l + r; } F id(){ return 0; } void solve(){ int n, k; cin >> n >> k; vector<ll> A(n); for(auto &a : A) cin >> a; lazy_segtree<S, op, e, F, mapping, composition, id> seg(n + 1); seg.set(0, 0); for(int i = 1; i <= n; i++){ ll a = A[i - 1]; seg.set(i, seg.prod(0, i)); seg.apply(max(0, i - k + 1), i, a); } cout << seg.all_prod() << endl; } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); }