Submission #1133906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133906		hoaphat1	Feast (NOI19_feast)	C++20	100 / 100	74 ms	14764 KiB

feast

#include<bits/stdc++.h>

using namespace std;

struct T {
	long long cost;
	int l, r;
	T(long long cost, int l, int r) : cost(cost), l(l), r(r) {
	}
	bool operator < (const T& other) const {
		return cost < other.cost;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("test.inp", "r", stdin);
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int l = 0, r = n - 1;
	while (l < n && a[l] <= 0) l++;
	while (r >= 0 && a[r] <= 0) r--;
	if (l > r) {
		cout << 0;
		return 0;
	}
	a = vector<int> (a.begin() + l, a.begin() + r + 1);
	n = (int)a.size();
	vector<T> t;
	vector<int> prev(n + 1, -1);
	vector<int> nxt(n + 1, -1);
	vector<long long> res(n);
	for (int i = 0; i < n; i++) {
		int j = i + 1;
		long long now = a[i];
		while (j < n && (a[i] > 0) == (a[j] > 0)) now += a[j++];
		t.push_back(T(now, i, j));
				
			nxt[i] = j;
			prev[j] = i;
		
		res[i] = -abs(now);
		i = j - 1;
	}
	if (n == 1) {
		cout << max(a[0], 0);
		return 0;
	}
	priority_queue<T> pq;
	long long ans = 0;
	for (int i = 0; i < (int) t.size(); i++) {
		if (t[i].cost > 0) ans += t[i].cost, --k;
		pq.push(T{-abs(t[i].cost), t[i].l, t[i].r});
//		cout << t[i].cost <<" " << t[i].l <<" " << t[i].r << endl;
	}
//	cout << k << " " << nxt[72] << endl;
	vector<int> flag(n + 1);
	while (!pq.empty() && k < 0) {
		/*
			a-x-b mn 
			a + b -> a + b + mn - x
		*/
		auto x = pq.top(); pq.pop();
		long long cost = x.cost;
		int l = x.l, r = x.r;
		int ll = prev[l], rr = nxt[r];
//	for (int i = 0; i < n; i++) cout << res[i] <<" "; cout << endl;
		if (res[l] != cost || flag[l] || flag[r]) continue;
//		cout << cost <<" " << l <<" " << r << " " << ll <<" " << rr << endl;
		k++;
		ans += cost;
		flag[l] = flag[r] = true;
		if (ll == -1) {
			long long val = res[r] - cost;
			res[l] = val;
			nxt[l] = rr;
			prev[rr] = l;
			pq.push(T{val, l, rr});
			continue;
		}
		if (rr == -1) {
			long long val = res[ll] - cost;
			res[ll] = val;
			nxt[ll] = r;
			prev[r] = ll;
			pq.push(T{val, ll, r});
			continue;
		}
		long long val = res[ll] + res[r] - cost;
		res[ll] = val;
		nxt[ll] = rr;
		prev[rr] = ll;
//		cout << "cal " << val <<" " << ll <<" " << rr << endl;
		pq.push(T{val, ll, rr});
	}
	cout << ans;
}

• 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