Submission #200082

#	Time	Username	Problem	Language	Result	Execution time	Memory
200082		dennisstar	Candies (JOI18_candies)	C++17	100 / 100	145 ms	11124 KiB

candies

#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
using namespace std;
typedef long long ll;

int N, chk[200010], l[200010], r[200010]; ll A[200010], ans;
priority_queue<pair<ll, int> > pq;


int main() {
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%lld", &A[i]), pq.em(A[i], i), l[i]=i-1, r[i]=i+1;
	A[0]=A[N+1]=-(1e16);
	for (int i=(N+1)/2; i; i--) {
		while (chk[pq.top().se]) pq.pop();
		auto k=pq.top(); pq.pop();
		ans+=k.fi; printf("%lld\n", ans);
		chk[l[k.se]]=chk[r[k.se]]=1;
		A[k.se]=A[l[k.se]]+A[r[k.se]]-A[k.se]; pq.em(A[k.se], k.se);
		l[k.se]=l[l[k.se]], r[l[k.se]]=k.se;
		r[k.se]=r[r[k.se]], l[r[k.se]]=k.se;
	}
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
candies.cpp:14:73: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%lld", &A[i]), pq.em(A[i], i), l[i]=i-1, r[i]=i+1;
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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