Submission #338767

#	Time	Username	Problem	Language	Result	Execution time	Memory
338767		wwdd	Candies (JOI18_candies)	C++14	100 / 100	326 ms	13796 KiB

candies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
vl w;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
	}
	multiset<ll,greater<ll> > bs[2],dis[2];
	ll cu = 0;
	for(int i=n-1;i>=0;i--) {
		int nu = 1-cu;
		bs[nu].insert(w[i]);
		dis[nu].insert(w[i]);
		ll dif = 0;
		while(!dis[nu].empty() && !dis[cu].empty() && (*dis[nu].begin()+dif) <= (*dis[cu].begin())) {
			auto wa = dis[nu].begin();
			auto wb = dis[cu].begin();
			dif += (*wa)-(*wb);
			bs[nu].erase(bs[nu].find(*wa));
			bs[nu].insert(*wb);
			dis[nu].erase(wa);
			dis[cu].erase(wb);
		}
		if(!dis[nu].empty()) {
			ll wa = *dis[nu].begin();
			bs[nu].insert(wa+dif);
			dis[nu].insert(wa+dif);
			bs[nu].erase(bs[nu].find(wa));
			dis[nu].erase(dis[nu].find(wa));
		}
		cu = nu;
	}
	ll ru = 0;
	for(auto& it: bs[cu]) {
		ru += it;
		cout << ru << '\n';
	}
}

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