Submission #516346

#	Time	Username	Problem	Language	Result	Execution time	Memory
516346		Leonardo_Paes	Candies (JOI18_candies)	C++17	0 / 100	1 ms	460 KiB

candies

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

typedef long long ll;
struct range{
	int l, r;
	ll on, off, delta;
	range(){}
	range(int &x, int &id){
		l = r = id;
		on = 0;
		off = x;
		delta = off - on;
	}
	void swp(){ swap(on, off); att(); }
	void att(){ delta = off - on; }
	bool operator<(const range &a) const { return delta < a.delta; }
};

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;
	cin >> n;
	vector<bool> is_corner(n+1), mark(n+1);
	vector<range> v(n+1);
	priority_queue<range> fila;
	for(int i=1; i<=n; i++){
		int x;
		cin >> x;
		fila.push(range(x, i));
		v[i] = range(x, i);
	}
	int k = 0;
	ll ans = 0;
	while(k < ((n+1)>>1)){
		range at = fila.top();
		fila.pop();
		//cout << at.l << " " << at.r << " " << fila.size() << endl;
		if(at.l == at.r){ if(mark[at.l]) continue; }
		else if(!(is_corner[at.l]&is_corner[at.r])) continue;
		k++;
		ans += at.delta;
		at.swp();
		if(at.l != 1){
			if(is_corner[at.l-1]){
				is_corner[at.l-1] = 0;
				at.on += v[at.l-1].on, at.off += v[at.l-1].off;
				at.l = v[at.l-1].l;
			}
			else{
				at.off += v[--at.l].off;
				mark[at.l] = 1;
			}
		}
		if(at.r != n){
			if(is_corner[at.r+1]){
				is_corner[at.r+1] = 0;
				at.on += v[at.r+1].on, at.off += v[at.r+1].off;
				at.r = v[at.r+1].r;
			}
			else{
				at.off += v[++at.r].off;
				mark[at.r] = 1;
			}
		}
		at.att();
		v[at.l] = v[at.r] = at;
		is_corner[at.l] = is_corner[at.r] = 1;
		//cout << at.l << " " << at.r << " " << at.on << " " << at.off << " " << at.delta << endl;
		cout << ans << "\n";
		fila.push(at);
	}
	return 0;
}

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