Submission #73675

#	Time	Username	Problem	Language	Result	Execution time	Memory
73675		mraron	Candies (JOI18_candies)	C++14	0 / 100	6 ms	632 KiB

candies

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	int n;
	cin>>n;
	vector<int> t(n);
	set<int> unused;
	vector<ll> cost(n);
	set<pair<ll, int>> cost_lst;
	
	for(int i=0;i<n;++i) {
		cin>>t[i];
		unused.insert(i);
		cost[i]=t[i];
		cost_lst.insert({cost[i], i});
	}
	
	ll ans=0;
	for(int j=0;j<(n+1)/2;++j) {
		auto best=(--cost_lst.end())->second;
		auto best_cost=(--cost_lst.end())->first;
		
		ans+=best_cost;
		
		unused.erase(best);
		cost_lst.erase({best_cost, best});
		
		cost[best]=-cost[best];
		
		auto it=unused.lower_bound(best);
		if(it!=unused.end()) {
			cost[best]+=cost[*it];
			cost_lst.erase({cost[*it], *it});
			unused.erase(it);
		}
		
		it=unused.lower_bound(best);
		if(it!=unused.begin()) {
			it--;
			cost[best]+=cost[*it];
			cost_lst.erase({cost[*it], *it});
			unused.erase(it);
		}
		
		unused.insert(best);
		cost_lst.insert({cost[best], best});
		
		cout<<ans<<"\n";
	}
	
	return 0;
}

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