제출 #1133898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133898		hoaphat1	Feast (NOI19_feast)	C++20	0 / 100	55 ms	14508 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];
	vector<T> t;
	vector<int> prev(n, -1);
	vector<int> nxt(n, -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++];
		if (i == 0 && now < 0) {
			i = j - 1;
			continue;
		}
		if (j == n && now < 0) break;
		t.push_back(T(now, i, j));
		if (j < n) {		
			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 << " " << pq.size() << endl;
	vector<int> flag(n);
	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 << endl;
		k++;
		ans += cost;
		if (ll == -1) {
			long long val = res[r] - cost;
			res[l] = val;
			flag[r] = true;
			pq.push(T{val, l, rr});
			continue;
		}
		if (rr == -1) {
			long long val = res[ll] - cost;
			flag[l] = true;
			res[ll] = val;
			pq.push(T{val, ll, r});
			continue;
		}
		long long val = res[ll] + res[r] - cost;
		res[ll] = val;
		flag[l] = flag[r] = true;
		pq.push(T{val, ll, rr});
	}
	cout << ans;
}

• 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