Submission #164749

#	Time	Username	Problem	Language	Result	Execution time	Memory
164749		oolimry	Candies (JOI18_candies)	C++14	100 / 100	966 ms	27512 KiB

candies

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;

set<ii> best;
set<long long> idx;
int main(){
	int n;
	cin >> n;
	long long arr[n];
	for(int i = 0;i < n;i++){
		cin >> arr[i];
		best.insert(ii(arr[i],i));
		idx.insert(i);
	}
	idx.insert(-1);
	idx.insert(n+1);
	long long ans = 0;
	for(int k = 1;k <= (n+1)/2;k++){
		set<ii>::iterator it = (--best.end());
		best.erase(it);
		idx.erase(it->second);
		
		ans += it->first;
		int s = it->second;
		
		long long r = *idx.upper_bound(s);
		long long l = *(--idx.lower_bound(s));
		arr[s] *= -1;
		if(l >= 0){
			arr[s] += arr[l];
			best.erase(ii(arr[l],l));
			idx.erase(l); 
		}
		if(r <= n-1){
			arr[s] += arr[r];
			best.erase(ii(arr[r],r));
			idx.erase(r); 
		}
		
		if(r <= n-1 && l >= 0){
			best.insert(ii(arr[s],s));
			idx.insert(s);
		}
		
		cout << ans << "\n";
	}
}

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