답안 #367973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367973 2021-02-19T04:29:21 Z chctxdy68 Candies (JOI18_candies) C++17
0 / 100
2 ms 512 KB
#include <bits/stdc++.h>
using namespace std;
long long a[200005];
set <pair <long long, long long>> choices; 
long long l[200005], r[200005];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	long long n; cin >> n;
	for (long long i = 1; i <= n; i++){
		cin >> a[i]; l[i] = i - 1; r[i] = i + 1;
		choices.insert(make_pair(-a[i], i));
	}
	long long ans = 0;
	for (long long c = 0; c < (n + 1) / 2; c++){
		pair <long long, long long> mx = *choices.begin();
		choices.erase(choices.begin());
		ans -= mx.first;
		long long id = mx.second, lf = l[id], rg = r[id];
		if (lf) choices.erase(make_pair(-a[lf], lf));
		if (rg <= n) choices.erase(make_pair(-a[rg], rg));
		if (lf) l[id] = l[lf]; 
		else l[id] = 0;
		if (rg <= n) r[id] = r[rg];
		else r[id] = n + 1;
		if (l[id]) r[l[id]] = id; 
		if (r[id] <= n) l[r[id]] = id;
		a[id] = a[lf] + a[rg] - a[id];
		choices.insert(make_pair(-a[id], id));
		cout << ans << "\n"; 
	}
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -