Submission #759329

#	Time	Username	Problem	Language	Result	Execution time	Memory
759329		deom	Candies (JOI18_candies)	C++17	0 / 100	2 ms	340 KiB

candies

#include <bits/stdc++.h>
#define endl "\n"
#define upgrade ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
struct candy {
	ll candy;
	ll left;
	ll right;
	ll check;
};

// 백업==사탕
int main() {
	ll n;
	cin >> n;
	// ll t = (n + 1) / 2;
	vector<candy>arr(n+10);
	priority_queue<pair<ll, ll>>pq;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].candy;
		pq.push({ arr[i].candy,i });
		arr[i].left = i - 1;
		arr[i].right = i + 1;
		arr[i].check = 0;
	}
	arr[0].candy = -1;
	arr[0].candy = 0;
	arr[n + 1].candy = -1;
	arr[n + 1].check = 0;
	ll ans = 0;
	for (int i = 0; i < (n + 1) / 2; i++) {
		while (arr[pq.top().second].check) {
			pq.pop();
		}
		pair<ll, ll>save{ pq.top().first,pq.top().second };
		pq.pop();
		arr[arr[save.second].left].check = 1;
		arr[arr[save.second].right].check = 1;
		ans += save.first;
		cout << ans << endl;
		arr[save.second].candy = arr[arr[save.second].left].candy + arr[arr[save.second].right].candy - arr[save.second].candy;
		pq.push({ arr[save.second].candy,save.second });
		arr[save.second].left = arr[arr[save.second].left].left;
		arr[arr[save.second].left].right = save.second;
		arr[save.second].right = arr[arr[save.second].right].right;
		arr[arr[save.second].right].left = save.second;
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92