結果

問題 No.2139 K Consecutive Sushi
コンテスト
ユーザー wanui
提出日時 2022-12-03 01:46:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 236 ms / 2,000 ms
コード長 5,365 bytes
コンパイル時間 2,073 ms
コンパイル使用メモリ 199,312 KB
最終ジャッジ日時 2025-02-09 04:37:55
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
#define debug1(a) { cerr<<#a<<":"<<a<<endl; }
#define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }
#define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }
#define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }
// clang-format on

ll N, K;
ll A[200005];
ll cum[200005];
// 自明なO(N^2) DP
namespace naivedp {
ll rangesum(ll l, ll r) {
    if (r < l) return 0;
    if (l == 0) return cum[r];
    return cum[r] - cum[l - 1];
}
// i番目を取らないときの最大の価値
ll dp(ll i) {
    if (i - K < 1) {
        return rangesum(1, i - 1);
    }

    ll ans = 0;
    for (ll j = i - K; j <= i - 1; j++) {
        ans = max(ans, dp(j) + rangesum(j + 1, i - 1));
    }
    return ans;
}
};  // namespace naivedp

using LST = ll;
class lazy_segment_tree {
    // 区間加算、区間最大値
   public:
    ll size;
    vector<LST> data;
    vector<LST> updates;
    LST default_value;
    lazy_segment_tree(ll n) {
        default_value = add_default();
        ll siz = 1;
        while (siz < n) {
            siz = siz * 2;
        }
        data.resize(siz * 2, default_value);
        updates.resize(data.size(), default_value);
        size = siz;
    }

    ~lazy_segment_tree() {}

    //--------
    LST compare(LST x, LST y) {
        return max(x, y);
    }
    LST compare_default() {
        return -INF;
    }
    LST add(LST x, LST y) {
        return x + y;
    }
    LST add_default() {
        return 0;
    }
    LST evaluate(LST u, ll l, ll r) {
        return u;
    }
    LST transferred(LST vl, LST vr, ll l, ll r, ll a, ll b, ll k) {
        return add(compare(vl, vr), updates[k]);
    }
    //--------

    void update(ll a, ll b, LST value) {
        if (a > b || a > size || b < 0) {
            return;
        }
        if (a < 0) {
            a = 0;
        }
        if (b > size) {
            b = size;
        }
        update_open(a, b + 1, 0, 0, size, value);
    }
    void update_open(ll a, ll b, ll k, ll l, ll r, LST value) {
        if (r <= a || b <= l) {
            // 共通要素がない
            return;
        }
        if (k >= size - 1) {
            // 末端
            data[k] = add(data[k], evaluate(value, l, r));
            return;
        }

        // 末端でないとき、一旦現在のupdatesを払い出し
        ll lk = 2 * k + 1;
        ll rk = 2 * k + 2;
        ll mid = (l + r) / 2;

        if (rk >= size - 1) {
            data[lk] = add(data[lk], evaluate(updates[k], l, mid));
            data[rk] = add(data[rk], evaluate(updates[k], mid, r));
        } else {
            updates[lk] = add(updates[lk], updates[k]);
            updates[rk] = add(updates[rk], updates[k]);
        }

        if (a <= l && r <= b) {
            // 完全に含んでいる
            data[k] = compare(add(data[lk], evaluate(updates[lk], l, mid)), add(data[rk], evaluate(updates[rk], mid, r)));
            updates[k] = value;
        } else {
            // 一部含む
            update_open(a, b, 2 * k + 1, l, mid, value);
            update_open(a, b, 2 * k + 2, mid, r, value);
            updates[k] = add_default();
            data[k] = transferred(add(data[lk], evaluate(updates[lk], l, mid)), add(data[rk], evaluate(updates[rk], mid, r)), l, r, a, b, k);
        }
    }
    LST query_open(ll a, ll b, ll k, ll l, ll r) {
        if (r <= a || b <= l) {
            // 共通要素がない
            return compare_default();
        }
        if (a <= l && r <= b) {
            // 完全に含んでいる
            return add(data[k], evaluate(updates[k], l, r));
        }
        if (k >= size - 1) {
            // 末端であるとき
            return data[k];
        }
        // 伝播すべき値がある
        LST vl = query_open(a, b, k * 2 + 1, l, (l + r) / 2);
        LST vr = query_open(a, b, k * 2 + 2, (l + r) / 2, r);
        return transferred(vl, vr, l, r, a, b, k);
    }

    LST query(ll a, ll b) {
        return query_open(a, b + 1, 0, 0, size);
    }
};

int main() {
    ioinit();
    cin >> N >> K;
    for (ll i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for (ll i = 1; i <= N; i++) {
        cum[i] = A[i] + cum[i - 1];
    }
    auto dpseg = lazy_segment_tree(N + 2);
    for (ll i = 1; i <= N + 1; i++) {
        if (i - K < 1) {
            dpseg.update(i, i, cum[i - 1]);
        } else {
            ll cur = dpseg.query(i - K, i - 1);
            dpseg.update(i, i, cur);
        }
        dpseg.update(1, i - 1, A[i]);
    }
    print(dpseg.query(N + 1, N + 1));
    return 0;
}
0