Submission #1134727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134727		nai0610	Feast (NOI19_feast)	C++20	0 / 100	1096 ms	1348 KiB

feast

#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const ld pi = atan(1.0L) * 4;

int n, k, a[maxn], res[maxn];

int main() {
    // freopen("../input.inp", "r", stdin);
    // freopen("output.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int i = 1;
    set<pair<int, int>> s;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    // Create initial segments
    while (i <= n) {
        int val = 0;
        int j = i;
        while (j <= n && a[i] * a[j] >= 0) val += a[j++];
        s.insert({i, val});
        i = j;
    }

    auto it = s.begin();
    // Remove negative segments at the beginning
    while (!s.empty() && (*it).second < 0) {
        s.erase(it);
        it = s.begin();
    }
    // Remove negative segments at the end
    if (!s.empty()) {
        it = prev(s.end());
        while (!s.empty() && (*it).second < 0) {
            s.erase(it);
            it = prev(s.end());
        }
    }

    int cnt = s.size() / 2 + 1;

    if (s.empty()) {
        fill(res, res + n + 1, 0);
        cout << res[k];
        return 0;
    } else if (cnt == 1) {
        fill(res + 1, res + n + 1, (*s.begin()).second);
        cout << res[k];
        return 0;
    }

    // Push segments into priority queue
    for (auto i = s.begin(); i != s.end(); i++) {
        q.push({abs((*i).second), (*i).first});
    }

    int cur = cnt;
    int sum = 0;
    for (auto i : s) {
        if (i.second > 0) sum += i.second;
    }
    fill(res + cnt, res + n + 1, sum);

    // Process merging
    for (int i = cnt - 1; i >= 1; i--) {
        // Remove negative segments from the set
        while (!s.empty() && (*s.begin()).second < 0) s.erase(s.begin());
        while (!s.empty() && (*prev(s.end())).second < 0) s.erase(prev(s.end()));

        // Merge segments to reduce count
        while (cur > i) {
            if (q.empty()) break; // Safety check
            auto p = q.top();
            q.pop();
            auto it = s.lower_bound({p.second, -mod});
            if (it == s.end()) continue;

            int id = (*it).first;

            // Handle boundary cases
            if (it == s.begin()) {
                auto nex = next(it);
                if (nex == s.end()) continue; // Avoid invalid access

                cur -= ((*it).second >= 0) + ((*nex).second >= 0);
                sum -= ((*it).second >= 0 ? (*it).second : 0) +
                       ((*nex).second >= 0 ? (*nex).second : 0);
                int nw = (*it).second + (*nex).second;
                cur += (nw >= 0);
                if (nw >= 0) sum += nw;

                s.erase(it);
                s.erase(nex);
                s.insert({id, nw});
                q.push({abs(nw), id});
            } else if (it == prev(s.end())) {
                auto pre = prev(it);
                if (pre == s.end()) continue;

                cur -= ((*it).second >= 0) + ((*pre).second >= 0);
                sum -= ((*it).second >= 0 ? (*it).second : 0) +
                       ((*pre).second >= 0 ? (*pre).second : 0);
                int nw = (*it).second + (*pre).second;
                cur += (nw >= 0);
                if (nw >= 0) sum += nw;

                s.erase(it);
                s.erase(pre);
                s.insert({id, nw});
                q.push({abs(nw), id});
            } else {
                auto pre = prev(it), nex = next(it);
                if (pre == s.end() || nex == s.end()) continue;

                cur -= ((*pre).second >= 0) + ((*it).second >= 0) + ((*nex).second >= 0);
                sum -= ((*pre).second >= 0 ? (*pre).second : 0) +
                       ((*it).second >= 0 ? (*it).second : 0) +
                       ((*nex).second >= 0 ? (*nex).second : 0);
                int nw = (*pre).second + (*it).second + (*nex).second;
                cur += (nw >= 0);
                if (nw >= 0) sum += nw;

                s.erase(pre);
                s.erase(it);
                s.erase(nex);
                s.insert({id, nw});
                q.push({abs(nw), id});
            }
        }
        res[i] = sum;
    }

    cout << res[k];
    return 0;
}

• Subtask 1: 0 / 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