oj.uz

Submission #73675

# Submission time Handle Problem Language Result Execution time Memory
73675 2018-08-28T17:15:26 Z mraron Candies (JOI18_candies) C++14
0 / 100
 6 ms 632 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 632 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 632 KB Output isn't correct
2 Halted 0 ms 0 KB -