Submission #894617

#	Time	Username	Problem	Language	Result	Execution time	Memory
894617		IWKR	Feast (NOI19_feast)	C++17	100 / 100	76 ms	25536 KiB

feast

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

#define int long long

int arr[300001];
int a[300001];
int s[300001];
int cost[300001];
int pre[300001];
int nex[300001];
bool mark[300001];
priority_queue<tuple<int, int, int>> pq;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int start = 0;
    int end = n - 1;
    while (start < n && arr[start] <= 0) {
        start++;
    }
    while (end >= 0 && arr[end] <= 0) {
        end--;
    }
    if (start > end) {
        cout << 0;
        return 0;
    }
    n = 0;
    for (int i = start; i <= end; i++) {
        a[++n] = arr[i];
    }
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    int last = 0;
    pre[0] = nex[n] = 1e9;
    for (int i = 1; i <= n; i++) {
        if (i > 1 && (a[i] > 0) != (a[i - 1] > 0)) {
            if (a[i - 1] > 0) {
                --k;
            }
            cost[i - 1] = -abs(s[i - 1] - s[last]);
            pre[i - 1] = last;
            nex[last] = i - 1;
            pq.emplace(cost[i - 1], last, i - 1);
            last = i - 1;
        }
    }
    --k;
    cost[n] = -abs(s[n] - s[last]);
    pre[n] = last;
    nex[last] = n;
    pq.emplace(cost[n], last, n);
    int ans = 0;
    while (!pq.empty() && k < 0) {
        int price, l, r;
        tie(price, l, r) = pq.top();
        pq.pop();
        if (mark[l] || mark[r] || price != cost[r]) {
            continue;
        }
        ++k;
        ans += cost[r];
        mark[l] = mark[r] = true;
        int ll = pre[l];
        int rr = nex[r];
        if (ll < rr && ll >= 0 && rr <= n) {
            pre[rr] = ll;
            nex[ll] = rr;
            cost[rr] += cost[l] - cost[r];
            cost[r] = -1e18;
        }
        if (ll < rr && ll >= 0 && rr <= n && !mark[ll] && !mark[rr]) {
            pq.emplace(cost[rr], ll, rr);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] > 0) {
            ans += a[i];
        }
    }
    cout << ans;
}

• 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