Submission #47325

#	Time	Username	Problem	Language	Result	Execution time	Memory
47325		szawinis	Candies (JOI18_candies)	C++17	100 / 100	190 ms	66832 KiB

candies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+1;
const ll INF = 1e17;

int n;
ll a[N], pre[N], nxt[N];
priority_queue<pair<ll, int> > pq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		if(i > 1) pre[i] = i-1;
		if(i < n) nxt[i] = i+1;
		pq.emplace(a[i], i);
	}
	ll ans = 0;
	for(int z = 1; z <= n+1 >> 1; z++) {
		while(pq.top().first != a[pq.top().second]) pq.pop();
		int i = pq.top().second;
		ans += a[i];
		cout << ans << '\n';
		int l = pre[i], r = nxt[i];
		nxt[i] = nxt[r];
		pre[i] = pre[l];
		pre[nxt[r]] = i;
		nxt[pre[l]] = i;
		if(l && r) a[i] = max(a[l] + a[r] - a[i], -INF);
      	else a[i] = -INF;
		a[l] = a[r] = -INF;
		pq.emplace(a[i], i);
	}
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  for(int z = 1; z <= n+1 >> 1; z++) {
                      ~^~

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