Submission #336457

#	Time	Username	Problem	Language	Result	Execution time	Memory
336457		ncduy0303	Feast (NOI19_feast)	C++17	100 / 100	105 ms	11140 KiB

feast

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

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

struct block {
    int l, r;
    ll sum;
} b[MAX_N];

int num = 0;

void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    for (int i = 0; i < n; i++) {
        b[num] = {num - 1, num + 1, 0};
        int j = i;
        while (j < n && (ll)a[i] * a[j] >= 0) b[num].sum += a[j++];
        i = j - 1;
        if (!(b[num].sum <= 0 && num == 0)) num++;
    }
    if (num > 0 && b[num - 1].sum <= 0) num--;
    if (num == 0) {
        cout << 0 << "\n";
        return;
    }
    b[0].l = b[num - 1].r = -1;
    int cnt = num / 2 + 1;
    priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq;
    for (int i = 0; i < num; i++) pq.push({abs(b[i].sum), i});
    vector<bool> vis(num);
    while (cnt > k) {
        auto [v, i] = pq.top(); pq.pop();
        if (vis[i]) continue;
        vis[i] = true;
        cnt--;

        if (b[i].l == -1) { 
			vis[b[i].r] = true;
			b[b[b[i].r].r].l = -1;
		}
		else if (b[i].r == -1) { 
			vis[b[i].l] = true;
			b[b[b[i].l].l].r = -1;
		}
		else {
			vis[b[i].r] = vis[b[i].l] = true;
			b[i].sum += b[b[i].l].sum + b[b[i].r].sum;
			if (b[b[i].l].l != -1) b[b[b[i].l].l].r = i;
			if (b[b[i].r].r != -1) b[b[b[i].r].r].l = i;
            b[i].l = b[b[i].l].l;
			b[i].r = b[b[i].r].r;
			vis[i] = 0;
			pq.push({abs(b[i].sum), i});
		}
    }
    ll ans = 0;
    for (int i = 0; i < num; i++) {
        if (vis[i] || b[i].sum <= 0) continue;
        ans += b[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();
    }
}

• 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