제출 #961065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961065		Pring	Candies (JOI18_candies)	C++17	100 / 100	428 ms	29904 KiB

candies

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else 
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;

const int MXN = 200005;
const ll INF = 3.9e18;
int n;
ll a[MXN], ans;
set<pil> pos;
multiset<pli> S;

void PRE() {
	FOR(i, 0, n + 2) {
		pos.insert(mp(i, a[i]));
		S.insert(mp(a[i], i));
	}
}

void miku() {
	cin >> n;
	FOR(i, 1, n + 1) cin >> a[i];
	a[0] = -INF;
	a[n + 1] = -INF;
	PRE();
	FOR(i, 0, n / 2 + n % 2) {
		// for (auto [v, j] : pos) debug(v, j);
		auto [val, p] = *S.rbegin();
		ans += val;
		auto it = pos.find(mp(p, val));
		auto itl = prev(it), itr = next(it);
		auto [l, vl] = *itl;
		auto [r, vr] = *itr;
		FOR($, 0, 3) {
			itl = pos.erase(itl);
		}
		S.erase(S.find(mp(val, p)));
		S.erase(S.find(mp(vl, l)));
		S.erase(S.find(mp(vr, r)));
		pos.insert(mp(l, vl + vr - val));
		S.insert(mp(vl + vr - val, l));
		cout << ans << '\n';
	}
}

int32_t main() {
	cin.tie(0) -> sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	miku();
	return 0;
}

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