Submission #123102

#	Time	Username	Problem	Language	Result	Execution time	Memory
123102		Mamnoon_Siam	Candies (JOI18_candies)	C++17	0 / 100	8 ms	632 KiB

candies

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int maxn = 2e5 + 5;

int N;
ll a[maxn];

struct node {
	ll val;
	node *l, *r;
	node () {
		val = 0;
		l = r = NULL;
	}
};

using llp = pair<ll, node*>;

multiset<llp> Q;

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	node *prev = NULL;
	for(int i = 1; i <= N; i++) {
		node *now = new node();
		now -> val = a[i];
		now -> l = prev;
		if(prev) now -> l -> r = now;
		Q.insert(llp(a[i], now));
		prev = now;
	}
	ll ans = 0;
	for(int i = 1; i <= (N - 1) / 2 + 1; i++) {
		// take best
		node* best = Q.rbegin() -> second;
		// update answer
		ans += best -> val;
		// create virtual elem
		node *now = new node();
		now -> val = -best -> val;
		int flag = 1;
		if(best -> l) {
			now -> val += best -> l -> val;
			now -> l = best -> l -> l;
			Q.erase(llp(best -> l -> val, best -> l));
			delete(best -> l);
		} else {
			flag = 0;
		}
		if(best -> r) {
			now -> val += best -> r -> val;
			now -> r = best -> r -> r;
			Q.erase(llp(best -> r -> val, best -> r));
			delete(best -> r);
		} else {
			flag = 0;
		}
		if(now -> l) now -> l -> r = now;
		if(now -> r) now -> r -> l = now;
		Q.erase(--Q.end());
		if(flag) {
			Q.insert(llp(now -> val, now));
		}
		cout << ans << endl;
	}
	return 0;
}

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