Submission #1270361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270361		SDAdzs1tg	Feast (NOI19_feast)	C++20	4 / 100	155 ms	31596 KiB

feast

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 5;
int n, k;
struct st{
    int t, l, r;
    bool operator< (const st a) const {
        if(abs(a.t) == abs(t)) return a.r < r;
        return abs(a.t) > abs(t);
    }
};
signed main () {
    cin >> n >> k;
    deque<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while(!a.empty() && a.back() <= 0) a.pop_back();
    while(!a.empty() && a.front() <= 0) a.pop_front();
    bool c = true;
    vector<int> b;
    b.push_back(0);
    for(int i = 0; i < a.size(); i++) {
        if(c && a[i] >= 0) {
            b.back() += a[i];
        }
        else if(!c && a[i] < 0) {
            b.back() += a[i];
        }
        else {
            b.push_back(a[i]);
            c = !c;
        }
    }
    n = b.size();
    int cnt = (n + 1) / 2;
    vector<int> p(n);
    vector<pair<int, int>> range(n);
    p[0] = b[0];
    for(int i = 1; i < n; i++) {
        p[i] = p[i - 1] + b[i];
    }
    for(int i = 0; i < n; i++) {
        range[i] = {i, i};
    }
    priority_queue<st> pq;
    for(int i = 0; i < n; i++) {
        pq.push({b[i], i, i});
    }
    int u = 0, v = n - 1;
    map<int, bool> vis[n];
    while(!pq.empty() && cnt > k) {
        st mm = pq.top();
        int t = mm.t;
        int l = mm.l;
        int r = mm.r;
        pq.pop();
        if(vis[l][r]) continue;
        vis[l][r] = true;
        if(l > u) {
            int ll = range[l - 1].first;
            int rr = range[l - 1].second;
            int d = 0;
            d += p[rr];
            if(ll > 0) d -= p[ll - 1];
            vis[ll][rr] = true;
            l = ll;
            t += d;
        }
        if(r < v) {
            int ll = range[r + 1].first;
            int rr = range[r + 1].second;
            int d = 0;
            d += p[rr];
            if(ll > 0) d -= p[ll - 1];
            vis[ll][rr] = true;
            r = rr;
            t += d;
        }
        range[l].first = range[r].first = l;
        range[l].second = range[r].second = r;
        if(t <= 0 && l == u) u = l;
        else if(t <= 0 && r == v) v = r;
        else pq.push({t, l, r});
        cnt--;
    }
    int ans = 0;
//    while(!pq.empty()) {
//        cout << pq.top().t << ' ';
//        pq.pop();
//    }
    while(!pq.empty()) {
        if(pq.top().t > 0 && !vis[pq.top().l][pq.top().r]) {
            ans += pq.top().t;
           // k--;
        }
        pq.pop();
    }
    cout << ans << '\n';
}

• 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