Submission #1300224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300224		danglayloi1	Feast (NOI19_feast)	C++20	100 / 100	177 ms	135404 KiB

feast

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

struct Node {
    ll sm = 0;
    ll pre = 0, suf = 0, res = 0;
    int l = 0, r = 0;
    int pr = -1, sf = -1; // prefix right idx, suffix left idx
    int rl = -1, rr = -1; // best subarray [rl,rr]
};

vector<Node> mx, mn;
vector<char> lz;
vector<ll> a;

Node make_leaf(ll val, int idx) {
    Node X;
    X.sm = val; X.l = X.r = idx;
    if (val > 0) {
        X.pre = X.suf = X.res = val;
        X.pr = X.sf = X.rl = X.rr = idx;
    } else {
        X.pre = X.suf = X.res = 0;
        X.pr = X.sf = X.rl = X.rr = -1;
    }
    return X;
}

Node mergeN(const Node &L, const Node &R) {
    Node P;
    P.sm = L.sm + R.sm;
    P.l = L.l; P.r = R.r;

    // prefix: choose between L.pre (idx L.pr) and L.sm + R.pre (idx R.pr)
    ll cand_pre_val = 0; int cand_pre_idx = -1;
    if (L.pr != -1) { cand_pre_val = L.pre; cand_pre_idx = L.pr; }
    // second candidate
    if (R.pr != -1) {
        ll v2 = L.sm + R.pre;
        if (v2 > cand_pre_val) { cand_pre_val = v2; cand_pre_idx = R.pr; }
    }
    P.pre = cand_pre_val; P.pr = cand_pre_idx;

    // suffix: choose between R.suf (idx R.sf) and L.suf + R.sm (idx L.sf)
    ll cand_suf_val = 0; int cand_suf_idx = -1;
    if (R.sf != -1) { cand_suf_val = R.suf; cand_suf_idx = R.sf; }
    if (L.sf != -1) {
        ll v2 = L.suf + R.sm;
        if (v2 > cand_suf_val) { cand_suf_val = v2; cand_suf_idx = L.sf; }
    }
    P.suf = cand_suf_val; P.sf = cand_suf_idx;

    // res: three candidates: L.res (L.rl), R.res (R.rl), cross (L.suf + R.pre) if both sides valid
    P.res = 0; P.rl = P.rr = -1;
    if (L.rl != -1) { P.res = L.res; P.rl = L.rl; P.rr = L.rr; }
    if (R.rl != -1 && R.res > P.res) { P.res = R.res; P.rl = R.rl; P.rr = R.rr; }
    if (L.sf != -1 && R.pr != -1) {
        ll cross = L.suf + R.pre;
        if (cross > P.res) {
            P.res = cross; P.rl = L.sf; P.rr = R.pr;
        }
    }
    // If none positive, P.res stays 0 and rl=-1
    return P;
}

void build(int nd, int l, int r) {
    if (l == r) {
        mx[nd] = make_leaf(a[l], l);
        mn[nd] = make_leaf(-a[l], l);
        return;
    }
    int mid = (l + r) >> 1;
    build(nd<<1, l, mid);
    build(nd<<1|1, mid+1, r);
    mx[nd] = mergeN(mx[nd<<1], mx[nd<<1|1]);
    mn[nd] = mergeN(mn[nd<<1], mn[nd<<1|1]);
}

void push(int nd, int l, int r) {
    if (!lz[nd]) return;
    swap(mx[nd], mn[nd]);
    if (l != r) {
        lz[nd<<1] ^= 1;
        lz[nd<<1|1] ^= 1;
    }
    lz[nd] = 0;
}

void flip(int nd, int l, int r, int L, int R) {
    push(nd, l, r);
    if (R < l || r < L) return;
    if (L <= l && r <= R) {
        swap(mx[nd], mn[nd]);
        if (l != r) { lz[nd<<1] ^= 1; lz[nd<<1|1] ^= 1; }
        return;
    }
    int mid = (l + r) >> 1;
    flip(nd<<1, l, mid, L, R);
    flip(nd<<1|1, mid+1, r, L, R);
    push(nd<<1, l, mid); push(nd<<1|1, mid+1, r);
    mx[nd] = mergeN(mx[nd<<1], mx[nd<<1|1]);
    mn[nd] = mergeN(mn[nd<<1], mn[nd<<1|1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    a.assign(n+1, 0);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    mx.assign(4*n+5, Node());
    mn.assign(4*n+5, Node());
    lz.assign(4*n+5, 0);

    build(1, 1, n);

    ll ans = 0, s = 0;
    for (int it = 0; it < m; ++it) {
        push(1, 1, n); // ensure root up-to-date
        if (mx[1].rl == -1) break; // no positive subarray left
        ll cur = mx[1].res;
        s += cur;
        ans = max(ans, s);
        flip(1, 1, n, mx[1].rl, mx[1].rr);
    }
    cout << ans << '\n';
    return 0;
}

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