Submission #882283

#	Time	Username	Problem	Language	Result	Execution time	Memory
882283		NK_	Candies (JOI18_candies)	C++17	0 / 100	1 ms	604 KiB

candies

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back

using ll = long long;

const ll INFL = ll(3e18);
const int INF = int(1e9) + 1008;

template<class T> using V = vector<T>;
using vi = vector<int>;
using vl = vector<ll>;

template<class T> using pq = priority_queue<T, vector<T>, less<T>>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N; int M = N;
	vl A(N); for(auto& x : A) cin >> x;
	
	if (N % 2 == 0) A.pb(0); 

	N = sz(A);

	vl ans(N, 0);
	for(int s = 0; s < 2; s++) {
		ll S = 0; int amt = 0; for(int i = s; i < N; i += 2) {
			S += A[i], amt++;
			// cout << amt << " => " << S << endl;
		}


		ans[amt] = max(ans[amt], S);

		ll P = 0, mn = (s == 0 ? 0 : INFL); int best = -1;
		pq<array<ll, 3>> q;
		for(int i = 0; i < N; i++) {
			P += ((i & 1) ^ s ? +1 : -1) * A[i];
			if (i % 2 == s) {
				q.push({P - mn, best, i});
			} else {
				if (P < mn) mn = P, best = i;
			}
		}

		// for(auto& x : A) cout << x << " ";
		// cout << endl;

		set<int> R = {INF};
		while(sz(q)) {
			auto [x, l, r] = q.top(); q.pop();


			// check if possible
			if (*R.lower_bound(l) <= r) continue;

			// cout << x << " " << l << " " << r << endl;

			S += x; amt--;
			// cout << amt << " " << S << endl;
			ans[amt] = max(ans[amt], S);

			for(int c = l + 1; c <= r; c++) {
				if (c % 2 == s) R.insert(c);
				else q.push({-A[c], -1, -1});
			}
		}
	}

	for(int i = 1; i <= (M + 1) / 2; i++) cout << ans[i] << nl;

	exit(0-0);
}

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