Submission #1228926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228926		trimkus	Feast (NOI19_feast)	C++20	4 / 100	157 ms	17020 KiB

feast

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


struct DSU {
    vector<int> e;
    vector<ll> sum;
    vector<int> l, r;
    DSU(int n) {
        e = vector<int>(n, -1);
        sum = vector<ll>(n);
        l = vector<int>(n);
        r = vector<int>(n);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    void unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) return; // neturetu reiket?
        if (e[x] > e[y]) swap(x, y);
        l[x] = min(l[x], l[y]);
        r[x] = max(r[x], r[y]);
        sum[x] += sum[y];
        e[x] += e[y];
        e[y] = x;
    }
};

void chmax(ll& x, ll y) {
    x = max(x, y);
}


int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    DSU dsu(N);
    for (int i = 0; i < N; ++i) {
        dsu.sum[dsu.get(i)] = a[i];
        dsu.l[dsu.get(i)] = i;
        dsu.r[dsu.get(i)] = i;
    }
    for (int i = 1; i < N; ++i) {
        if (dsu.sum[dsu.get(i)] >= 0 && dsu.sum[dsu.get(i - 1)] >= 0) {
            dsu.unite(i, i - 1);
        } else if (dsu.sum[dsu.get(i)] <= 0 && dsu.sum[dsu.get(i - 1)] <= 0) {
            dsu.unite(i, i - 1);
        }
    }
    priority_queue<pair<ll, int>> pq;
    vector<int> vis(N);
    for (int i = 0; i < N; ++i) {
        if (vis[dsu.get(i)]) continue;
        // cout << dsu.sum[dsu.get(i)] << " ";
        vis[dsu.get(i)] = 1;
        pq.push({dsu.sum[dsu.get(i)], i});
    }
    // cout << "\n";
    auto get_right = [&](int i) -> int{
        i = dsu.get(i);
        ll mx = dsu.sum[i];
        ll tot = dsu.sum[i];
        if (dsu.r[i] + 1 >= N) return -1;
        int j = dsu.get(dsu.r[i] + 1);
        tot += dsu.sum[j];
        if (dsu.r[j] + 1 >= N) return -1;
        j = dsu.r[j] + 1;
        tot += dsu.sum[j];
        mx = max(mx, dsu.sum[j]);
        if (tot < mx) return -1;
        return j;
    };
    auto get_left = [&](int i) -> int{
        i = dsu.get(i);
        ll mx = dsu.sum[i];
        ll tot = dsu.sum[i];
        if (dsu.l[i] - 1 < 0) return -1;
        int j = dsu.get(dsu.l[i] - 1);
        tot += dsu.sum[j];
        if (dsu.l[j] - 1 < 0) return -1;
        j = dsu.l[j] - 1;
        tot += dsu.sum[j];
        mx = max(mx, dsu.sum[j]);
        if (tot < mx) return -1;
        return j;
    };
    while (pq.size()) {
        ll d = pq.top().first;
        int i = pq.top().second;
        pq.pop();
        if (d <= 0) continue;
        // cout << d << "\n";
        bool done = false;
        if (get_right(i) != -1) {
            i = dsu.get(i);
            // cout << i << " " << dsu.r[i] + 1 << " -> ";
            dsu.unite(dsu.r[i] + 1, i);
            i = dsu.get(i);
            // cout << i << " " << dsu.r[i] + 1 << "\n";
            dsu.unite(dsu.r[i] + 1, i);
            done = true;
        }
        if (get_left(i) != -1) {
            i = dsu.get(i);
            dsu.unite(dsu.l[i] - 1, i);
            i = dsu.get(i);
            dsu.unite(dsu.l[i] - 1, i);
            done = true;
        }
        if (done) {
            pq.push({-dsu.sum[dsu.get(i)], i});
        }
    }
    set<int> st;
    for (int i = 0; i < N; ++i) {
        int j = dsu.get(i);
        if (st.count(j)) continue;
        st.insert(j);
        // cout << dsu.sum[j] << " ";
        pq.push({dsu.sum[j], j});
    }
    // cout << "\n";
    ll res = 0;
    for (int i = 0; i < K && pq.size(); ++i) {
        ll d = pq.top().first;
        pq.pop();
        if (d <= 0) continue;
        res += d;
    }
    cout << res << "\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