oj.uz

Submission #486614

# Submission time Handle Problem Language Result Execution time Memory
486614 2021-11-12T06:22:56 Z ez_ioi Candies (JOI18_candies) C++17
0 / 100
 1 ms 460 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mxN = 2e5 + 5, mod = 1e9 + 7, LOG = 20;

int n;
pair <int, int> cons[mxN];
ll a[mxN];

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	set <pair <ll, int> > st;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		cons[i] = {i - 1, i + 1};
		st.insert({a[i], i});
	}
	ll ans = 0;
	for (int i = 1; i <= (n + 1) / 2; ++i) {
		auto x = *(--st.end());
		ans += x.first;
		st.erase(x);
		int lb = cons[x.second].first, rb = cons[x.second].second;
		if (lb) st.erase({a[lb], lb}); 
		if (rb <= n) st.erase({a[rb], rb}); 
		if (lb && rb <= n) {
			a[x.second] = a[lb] + a[rb] - a[x.second];
			st.insert({a[x.second], x.second});
			cons[x.second] = {cons[lb].first, cons[rb].second};
			cons[cons[lb].first].second = x.second;
			cons[cons[rb].second].first = x.second;
		}
		else {
			cons[cons[lb].first].second = cons[rb].second;
			cons[cons[rb].second].first = cons[lb].first;
		}
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -