제출 #1158185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158185		pacman	Candies (JOI18_candies)	C++20	0 / 100	13 ms	752 KiB

candies

#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int maxn = 2e5 + 100;

int n, a[maxn], ans = 0;
set<pair<int ,int>> s;
set<int> active;


void in(){
	cin >> n;
	for(int i = 0 ;i < n; i++){
		cin >> a[i];
		s.insert({a[i], i});
		active.insert(i);
	}
}


void Engine(){
	while(active.size() > 1){
		pair<int ,int> v = *s.rbegin();
		s.erase(*s.rbegin());
		ans += v.first;
		cout << ans << "\n";
		if(active.size() == 1){
			break;
		}
		if(v.second == (*active.begin())){
			active.erase(*active.begin());
			s.erase({a[*active.begin()], *active.begin()});
			active.erase(*active.begin());
			continue;
		}
		if(v.second == (*active.rbegin())){
			active.erase(*active.rbegin());
			s.erase({a[*active.rbegin()], *active.rbegin()});
			active.erase(*active.rbegin());
			continue;
		}
		active.erase(v.second);
		auto ind = lower_bound(active.begin(), active.end(), v.second);
		auto nxt = ind;
		auto pre = prev(ind);
		s.erase({a[*nxt], *nxt});
		s.erase({a[*pre], *pre});
		active.erase(nxt), active.erase(pre);
		a[v.second] = a[*pre] + a[*nxt] - a[v.second];
		s.insert({a[v.second], v.second});
		active.insert(v.second);
	}
}


int32_t main(){

	ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);

	in();
	Engine();

	return 0;
}

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