Submission #361941

#	Time	Username	Problem	Language	Result	Execution time	Memory
361941		cheissmart	Candies (JOI18_candies)	C++14	100 / 100	399 ms	18308 KiB

candies

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	V<ll> a(n);
	set<int> alive;
	priority_queue<pair<ll, int>> pq;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		alive.insert(i);
		pq.push({a[i], i});
	}
	ll ans = 0;
	for(int i = 0; i < (n + 1) / 2; i++) {
		auto p = pq.top(); pq.pop();
		if(alive.count(p.S) == 0) {
			i--;
			continue;
		}
		auto it = alive.find(p.S);
		ans += p.F;
		if(it != alive.begin() && next(it) != alive.end()) {
			int l = *prev(it), r = *next(it);
			alive.erase(l), alive.erase(r);
			a[p.S] = a[l] + a[r] - a[p.S];
			pq.push({a[p.S], p.S});
		} else {
			if(it != alive.begin()) alive.erase(prev(it));
			if(next(it) != alive.end()) alive.erase(next(it));
			alive.erase(it);
		}
		cout << ans << '\n';
	}

}

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