Submission #330347

#	Time	Username	Problem	Language	Result	Execution time	Memory
330347		jungsnow	Feast (NOI19_feast)	C++14	4 / 100	1095 ms	13036 KiB

feast

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;
using ll = long long;

const int maxn = 500100;

typedef pair<ll, int> ii;

int N, M, K;
ll A[maxn], L[maxn], R[maxn];
set<ii> s;

int main() {
//    freopen("feast.inp", "r", stdin);
//    freopen("feast.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    while (N--) {
        int V; cin >> V;
        if (M == 0) {
            if (V > 0) A[++M] = V;
            continue;
        }
        if ((A[M] > 0) == (V > 0)) A[M] += V;
        else A[++M] = V;
    }
    if (A[M] < 0) {
        A[M] = 0;
        --M;
    }
    int Cn = 0;
    for (int i = 1; i <= M; ++i) {
        Cn += (A[i] > 0);
        L[i] = i - 1; R[i] = i + 1;
        s.insert(ii(abs(A[i]), i));
    }
    R[M] = 0;
    while (Cn > K) {
        ii Cur = *s.begin(); s.erase(Cur);
        int i = Cur.y;
        ll Val = A[i], LL = L[i], RR = R[i];
        if (A[i] > 0) Cn--;
        if (LL) {
            if (A[LL] > 0) Cn--;
            s.erase(ii(A[LL], LL));
            Val += A[LL];
            if (L[LL]) R[L[LL]] = i;
        }
        if (RR) {
            if (A[RR] > 0) Cn--;
            s.erase(ii(A[RR], RR));
            Val += A[RR];
            if (R[RR]) L[R[RR]] = i;
        }
        A[i] = Val;
        A[LL] = A[RR] = 0;
        if (L[i] == 0 && A[i] < 0) {
            L[R[i]] = 0;
            A[i] = 0;
        } else if (R[i] == 0 && A[i] < 0) {
            R[L[i]] = 0;
            A[i] = 0;
        } else s.insert(ii(abs(A[i]), i));
        Cn += (A[i] > 0);
    }
    ll Ans = 0;
    for (auto i : s) {
        Ans += max(A[i.y], 0ll);
    }
    cout << Ans << '\n';
    return 0;
}

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