Submission #61660

#	Time	Username	Problem	Language	Result	Execution time	Memory
61660		cki86201	Candies (JOI18_candies)	C++11	100 / 100	275 ms	9460 KiB

candies

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

int N;
ll A[200020];
int nxt[200020], pre[200020], chk[200020];

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++) scanf("%lld", A+i);
	for(int i=1;i<=N+1;i++) pre[i] = i-1;
	for(int i=0;i<=N;i++) nxt[i] = i+1;
	nxt[N+1] = pre[0] = -1;
	A[0] = A[N+1] = -1e18;
	priority_queue <pll> pq; ll ans = 0;
	for(int i=1;i<=N;i++) pq.push(pll(A[i], i));
	for(int i=1;i<=(N+1)/2;i++) {
		pll t = pq.top(); pq.pop();
		if(chk[t.Se]) { --i; continue; }
		ans += t.Fi;
		int idx = (int)t.Se;
		int pr = pre[idx];
		int nx = nxt[idx];
		chk[pr] = chk[nx] = 1;
		A[idx] = -A[idx] + A[pr] + A[nx];
		pq.push(pll(A[idx], idx));
		nxt[idx] = nxt[nx];
		if(nxt[nx] != -1) pre[nxt[nx]] = idx;
		pre[idx] = pre[pr];
		if(pre[pr] != -1) nxt[pre[pr]] = idx;
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
candies.cpp:38:29: 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);
                        ~~~~~^~~~~~~~~~~~~

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