Submission #810328

#	Time	Username	Problem	Language	Result	Execution time	Memory
810328		vuavisao	Feast (NOI19_feast)	C++17	100 / 100	70 ms	12152 KiB

feast

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const ll N = 3e5 + 10;
const ll INF = 1e18;

struct dsu {
    ll n = 0;
    vector<ll> parent = {};
    
    void resize(ll _n) {
        n = _n; 
        parent.resize(n + 10); for(ll i = 1; i <= n; ++ i) parent[i] = i;
    }
    dsu() {};
    dsu(ll _n) { this -> resize(_n); };

    ll ancestor(ll u) {
        if(parent[u] == u) return u;
        return parent[u] = ancestor(parent[u]);
    }

    bool join(ll u, ll v) {
        u = ancestor(u); v = ancestor(v);
        if(u == v) return false;
        parent[v] = u;
        return true;
    }
};

struct state {
    ll val = 0, idx = 0;
    state() {};
    state(ll _val, ll _idx) : val(_val), idx(_idx) {}; 

    bool operator < (const state& other) const {
        return abs(this -> val) > abs(other.val);
    }
};

ll n, k;
ll a[N];

ll nxt[N];
ll res;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> k;
    for(ll i = 1; i <= n; ++ i) cin >> a[i];
    vector<ll> List = {};
    for(ll i = 1, j = 1; i <= n; i = j) {
        ll s = 0;
        while(j <= n && a[i] * a[j] >= 0) {
            s += a[j];
            ++ j;
        }
        // cout << s << '\n';
        List.push_back(s);
    }
    if(!List.empty() && List.back() < 0) List.pop_back();
    if(!List.empty() && List.front() < 0) {
        reverse(List.begin(), List.end());
        List.pop_back();
    }
    n = (ll) List.size();
    ll have_p = 0; 
    priority_queue<state> pq = {};
    for(ll i = 1; i <= n; ++ i) {
        a[i] = List[i - 1];
        nxt[i] = i + 1;
        if(a[i] >= 0) {
            ++ have_p;
        }
        pq.push(state(a[i], i));
    }
    dsu dsu(n);
    while(!pq.empty() && have_p > k) {
        ll val = pq.top().val, idx = pq.top().idx;
        pq.pop();
        if(val != a[idx]) continue;
        if(val >= 0) -- have_p;
        if(idx > 1) {
            ll le = dsu.ancestor(idx - 1); 
            val += a[le];
            if(a[le] >= 0) -- have_p;
            dsu.join(le, idx); 
            a[idx] = - INF; nxt[le] = nxt[idx]; idx = le;
        }
        ll ri = nxt[idx];
        if(ri <= n) {
            val += a[ri];
            if(a[ri] >= 0) -- have_p;
            dsu.join(idx, ri); 
            a[ri] = - INF; nxt[idx] = nxt[ri];
        }
        if(val >= 0) ++ have_p;
        a[idx] = val; 
        if(val < 0 && (idx == 1 || nxt[idx] == n + 1)) continue;
        pq.push(state(val, idx));
    }
    ll res = 0;
    while(!pq.empty()) {
        ll val = pq.top().val, idx = pq.top().idx;
        pq.pop();
        if(val < 0 || val != a[idx]) continue;
        // cout << val << ' ' << idx << '\n';
        res += val;
    }
    cout << res;
    return (0 ^ 0);
}

/// Code by vuavisao

• 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