Submission #669283

#	Time	Username	Problem	Language	Result	Execution time	Memory
669283		dsyz	Candies (JOI18_candies)	C++17	100 / 100	110 ms	11956 KiB

candies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll arr[N + 2];
	bool used[N + 2];
	ll l[N + 2];
	ll r[N + 2];
	priority_queue<pair<ll,ll> > pq;
	memset(used,0,sizeof(used));
	for(ll i = 1;i <= N;i++){
		cin>>arr[i];
		l[i] = i - 1;
		r[i] = i + 1;
		pq.push(make_pair(arr[i],i));
	}
	arr[0] = -1e15;
	arr[N + 1] = -1e15;
	l[0] = 0;
	r[0] = 1;
	l[N + 1] = N;
	r[N + 1] = N + 1;
	ll sum = 0;
	for(ll j = 0;j < (N + 1) / 2;j++){
		while(!pq.empty() && used[pq.top().second] == 1){
			pq.pop();
		}
		ll value = pq.top().first;
		ll i = pq.top().second;
		pq.pop();
		sum += value;
		cout<<sum<<'\n';
		arr[i] = arr[l[i]] + arr[r[i]] - arr[i];
		used[l[i]] = 1;
		used[r[i]] = 1;
		pq.push(make_pair(arr[i],i));
		l[i] = l[l[i]];
		r[l[i]] = i;
		r[i] = r[r[i]];
		l[r[i]] = i;
	}
}

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