Submission #129841

#	Time	Username	Problem	Language	Result	Execution time	Memory
129841		RockyB	Candies (JOI18_candies)	C++17	0 / 100	4 ms	508 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 ("res.txt", "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;
	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];
		if (p > 1) {
			x += c[L[p - 1]];
			{
				// if (j == 2) cerr << l << ' ' << r << " -> " << c[L[p - 1]] << nl;
			}
			l = L[p - 1];
			st.erase({c[L[p - 1]], L[p - 1]});
		}
		if (R[p] < n) {
			x += c[R[p] + 1];
			// if (j == 2) cerr << l << ' ' << r << " -> " << c[R[p] + 1] << nl;
			r = R[R[p] + 1];
			st.erase({c[R[p] + 1], R[p] + 1});
		}

		L[r] = l;
		R[l] = r;
		c[l] = x;
		st.insert({x, l});
		
		/*cerr << ans << ' ' << x << " -> \n";
		for (auto it : st) cerr << it.f << ' ' << it.s << nl;
		cerr << nl;*/

		// cout << ans << nl;

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

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