oj.uz

답안 #123102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123102 2019-06-30T08:41:04 Z Mamnoon_Siam Candies (JOI18_candies) C++17
0 / 100
 8 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int maxn = 2e5 + 5;

int N;
ll a[maxn];

struct node {
	ll val;
	node *l, *r;
	node () {
		val = 0;
		l = r = NULL;
	}
};

using llp = pair<ll, node*>;

multiset<llp> Q;

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	node *prev = NULL;
	for(int i = 1; i <= N; i++) {
		node *now = new node();
		now -> val = a[i];
		now -> l = prev;
		if(prev) now -> l -> r = now;
		Q.insert(llp(a[i], now));
		prev = now;
	}
	ll ans = 0;
	for(int i = 1; i <= (N - 1) / 2 + 1; i++) {
		// take best
		node* best = Q.rbegin() -> second;
		// update answer
		ans += best -> val;
		// create virtual elem
		node *now = new node();
		now -> val = -best -> val;
		int flag = 1;
		if(best -> l) {
			now -> val += best -> l -> val;
			now -> l = best -> l -> l;
			Q.erase(llp(best -> l -> val, best -> l));
			delete(best -> l);
		} else {
			flag = 0;
		}
		if(best -> r) {
			now -> val += best -> r -> val;
			now -> r = best -> r -> r;
			Q.erase(llp(best -> r -> val, best -> r));
			delete(best -> r);
		} else {
			flag = 0;
		}
		if(now -> l) now -> l -> r = now;
		if(now -> r) now -> r -> l = now;
		Q.erase(--Q.end());
		if(flag) {
			Q.insert(llp(now -> val, now));
		}
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -