oj.uz

Submission #200081

# Submission time Handle Problem Language Result Execution time Memory
200081 2020-02-05T09:47:21 Z dennisstar Candies (JOI18_candies) C++17
0 / 100
 6 ms 376 KB 
#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;
		l[k.se]=r[r[k.se]], l[r[k.se]]=k.se;
	}
	return 0;
}

Compilation message

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -