Submission #1209999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209999		blazer	Feast (NOI19_feast)	C++20	59 / 100	1096 ms	17992 KiB

feast

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegmentTree {
    int n;
    vector<ll> t;
    const ll NEG_INF = LLONG_MIN / 2;
    SegmentTree(int size) {
        n = 1;
        while (n < size) n <<= 1;
        t.assign(2 * n, NEG_INF);
    }
    void update(int pos, ll val) {
        pos += n;
        t[pos] = val;
        for (pos /= 2; pos > 0; pos /= 2)
            t[pos] = max(t[2 * pos], t[2 * pos + 1]);
    }
    ll query(int l, int r) {
        ll res = NEG_INF;
        l += n; r += n;
        while (l <= r) {
            if ((l & 1) == 1) res = max(res, t[l++]);
            if ((r & 1) == 0) res = max(res, t[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    vector<ll> prefix(N + 1, 0);
    for (int i = 1; i <= N; i++) prefix[i] = prefix[i - 1] + A[i - 1];

    vector<ll> dp(N + 1, 0);

    for (int k = 1; k <= K; k++) {
        SegmentTree seg(N + 1);
        for (int i = 0; i <= N; i++)
            seg.update(i, dp[i] - prefix[i]);

        vector<ll> new_dp(N + 1, 0);
        new_dp[0] = 0;
        for (int i = 1; i <= N; i++) {
            ll val = seg.query(0, i - 1) + prefix[i];
            new_dp[i] = max(new_dp[i - 1], val);
        }
        dp.swap(new_dp);
    }

    cout << dp[N] << "\n";
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29