Submission #251845

#	Time	Username	Problem	Language	Result	Execution time	Memory
251845		lyc	Candies (JOI18_candies)	C++14	0 / 100	3 ms	640 KiB

candies

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<long long,int>;

const int mxN = 2e5+5;

int N;
multiset<ii> ms;
map<int,long long> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    FOR(i,1,N){
		int A; cin >> A;
		ms.insert(ii(A,i));
		mp[i] = A;
	}
	
	long long ans = 0;
	FOR(_i,1,(N+1)/2){
		auto i = prev(ms.end());
		ans += i->first;
		auto y = mp.find(i->second);
		ii nw = ii(-i->first, i->second);
		
		bool ins = 0;
		if (y != mp.begin()) {
			ins = 1;
			auto x = prev(y);
			ms.erase(ii(x->second,x->first));
			nw.first += x->second;
			mp.erase(x);
		}
		if (next(y) != mp.end()) {
			ins = 1;
			auto z = next(y);
			ms.erase(ii(z->second,z->first));
			nw.first += z->second;
			mp.erase(z);
		}
		
		ms.erase(i);
		mp.erase(y);
		if (ins) {
			ms.insert(nw);
			mp[nw.second] = nw.first;
		}
		cout << ans << '\n';
	}
}

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