Submission #129859

#	Time	Username	Problem	Language	Result	Execution time	Memory
129859		RockyB	Candies (JOI18_candies)	C++17	0 / 100	3 ms	632 KiB

candies

#include <bits/stdc++.h>

#define f first
#define s second

#define sz(x) (int)x.size()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define nl '\n'
#define ioi exit(0);

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 7;

int n;
int a[N];

ll c[N];
int L[N], R[N];

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	#ifdef IOI
		freopen ("in.txt", "r", stdin);
		freopen ("A.out", "w", stdout);
	#endif
	cin >> n;
	multiset < pair <ll, int> > st;
	rep(i, 1, n) {
		cin >> a[i];
		st.insert({a[i], i});
		c[i] = a[i];
		L[i] = R[i] = i;
	}
	ll sum = 0;
	int S = 1, E = n;
	rep(j, 1, (n + 1) / 2) {
		ll ans = st.rbegin() -> f;
		int p = st.rbegin() -> s;
		st.erase(--st.end());
		ll x = -ans;

		int l = p, r = R[p];
		int f = 0;
		if (p > S) {
			x += c[L[p - 1]];
			f++;
			l = L[p - 1];
			st.erase({c[L[p - 1]], L[p - 1]});
		}
		if (R[p] < E) {
			x += c[R[p] + 1];
			f++;
			r = R[R[p] + 1];
			st.erase({c[R[p] + 1], R[p] + 1});
		}

		c[l] = x;
		L[r] = l;
		R[l] = r;
		
		if (f == 2) {
			st.insert({x, l});
		}
		else {
			if (p == S) S += 2;
			else E -= 2;
		}

		/*cerr << p << ' ' << S << ' ' << E << nl;
		cerr << ans << ' ' << x << " -> \n";	
		for (auto it : st) cerr << it.f << ' ' << it.s << nl;
		cerr << nl;*/

		// cout << ans << nl;

		sum += ans;
		cout << sum << nl;
	}
	ioi
}

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