Submission #336453

#	Time	Username	Problem	Language	Result	Execution time	Memory
336453		ncduy0303	Feast (NOI19_feast)	C++17	0 / 100	234 ms	262148 KiB

feast

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

struct block {
    int l, r;
    ll sum;
};

void solve() {
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    deque<block> dq;
    for (int i = 0, num = 0; i < n;) {
        dq.push_back({-1, -1, 0});
        int j = i;
        while (j < n && a[j] * a[i] >= 0) dq.back().sum += a[j++];
        i = j;
    }
    if (dq.size() && dq.front().sum <= 0) dq.pop_front();
    if (dq.size() && dq.back().sum <= 0) dq.pop_back();
    if (dq.size()) dq.front().l = dq.back().r = -1;
    n = dq.size();
    for (int i = 0; i < n; i++) {
        if (i > 0) dq[i].l = i - 1;
        if (i < n - 1) dq[i].r = i + 1;
    }
    priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq;
    for (int i = 0; i < n; i++) pq.push({abs(dq[i].sum), i});
    vector<bool> vis(n);
    int cnt = n / 2 + 1; // no. of positive values in deque
    for (auto cur : dq) cerr << cur.sum << " ";
    cerr << "\n";
    while (cnt > m) {
        auto [v, i] = pq.top(); pq.pop();
        if (vis[i]) continue;
        vis[i] = true;
        cnt--;

        if (dq[i].l == -1) {
            vis[dq[i].r] = true;
            dq[dq[dq[i].r].r].l = -1;
        }
        else if (dq[i].r == -1) {
            vis[dq[i].l] = true;
            dq[dq[dq[i].l].l].r = -1;
        }
        else {
            vis[dq[i].l] = vis[dq[i].r] = true;
            dq[i].sum += dq[dq[i].l].sum + dq[dq[i].r].sum;
            if (dq[dq[i].l].l != -1) dq[dq[dq[i].l].l].r = i;
            if (dq[dq[i].r].r != -1) dq[dq[dq[i].r].r].l = i;
            dq[i].l = dq[dq[i].l].l;
            dq[i].r = dq[dq[i].r].r;
            vis[i] = false;
            pq.push({abs(dq[i].sum), i});
        }

        for (auto cur : dq) cerr << cur.sum << " ";
        cerr << "\n";
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i] || dq[i].sum <= 0) continue;
        ans += dq[i].sum;
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Compilation message (stderr)

feast.cpp: In function 'void solve()':
feast.cpp:23:21: warning: unused variable 'num' [-Wunused-variable]
   23 |     for (int i = 0, num = 0; i < n;) {
      |                     ^~~

• 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