Submission #1127474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127474		DylanSmith	Candies (JOI18_candies)	C++17	100 / 100	605 ms	15532 KiB

candies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)

mt19937 rng;

vector<ll> merge(vector<ll> a, vector<ll> b) {
	if (a.empty() || b.empty()) return {};
	int i = 1, j = 1;
	vector<ll> res = {a[0] + b[0]};
	while (i < sz(a) || j < sz(b)) {
		if (j == sz(b) || i < sz(a) && a[i] - a[i - 1] > b[j] - b[j - 1]) {
			res.pb(a[i] - a[i - 1] + res[sz(res) - 1]);
			i++;
		} else {
			res.pb(b[j] - b[j - 1] + res[sz(res) - 1]);
			j++;
		}
	}
	return res;
}

vector<ll> vMax(vector<ll> a, vector<ll> b) {
	for (int i = 0; i < sz(b); i++) {
		if (sz(a) == i) a.pb(LLONG_MIN);
		a[i] = max(a[i], b[i]);
	}
	return a;
}

vector<vector<vector<ll>>> search(vector<int> a) {
	if (sz(a) == 1) {
		vector res(2, vector<vector<ll>>(2, {0}));
		res[0][0].pb(a[0]);
		return res;
	}
	int mid = sz(a) / 2;
	vector<int> aL, aR;
	for (int i = 0; i < mid; i++) aL.pb(a[i]);
	for (int i = mid; i < sz(a); i++) aR.pb(a[i]);
	auto left = search(aL), right = search(aR);
	vector res(2, vector<vector<ll>>(2));
	for (int l = 0; l < 2; l++) {
		for (int r = 0; r < 2; r++) {
			res[l][r] = vMax(res[l][r], merge(left[l][0], right[1][r]));
			res[l][r] = vMax(res[l][r], merge(left[l][1], right[0][r]));
			res[0][0] = vMax(res[0][0], res[l][r]);
		}
	}
	vector<vector<vector<ll>>>().swap(left);
	vector<vector<vector<ll>>>().swap(right);
	return res;
}

void solve() {
	int N; cin >> N;
	vector<int> a(N);
	for (int i = 0; i < N; i++) cin >> a[i];
	auto res = search(a);
	for (int i = 1; i < sz(res[0][0]); i++) {
		cout << res[0][0][i] << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());

    solve();

    return 0;
}

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