Submission #683608

#	Time	Username	Problem	Language	Result	Execution time	Memory
683608		gediminas	Candies (JOI18_candies)	C++17	100 / 100	335 ms	11948 KiB

candies

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

/*input
5
3
5
1
7
6
*/
/*input
20
623239331
125587558
908010226
866053126
389255266
859393857
596640443
60521559
11284043
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724
*/
long long a[200'000];

struct rez {
	// 0 - not included
	// 1 - might be included
	vector<long long> v[2][2];
};
rez rek(int pr, int pab) {
	if (pr >= pab)
		return rez{{{{0}, {0}}, {{0}, {0}}}};

	if (pr + 1 == pab) {
		rez r{{{{0}, {0}}, {{0}, {0, a[pr]}}}};
		return r;
	}

	int mi = (pr + pab) / 2;
	auto v = rek(pr, mi);
	auto w = rek(mi, pab);

	rez r;

	int n = (pab - pr + 1) / 2;

	for (int x = 0; x < 2; ++x) {
		for (int y = 0; y < 2; ++y) {
			if (r.v[x][y].empty()) {
				r.v[x][y].push_back(0);
			}

			for (int t = 0; t < 2; ++t) {
				int vi = 0, wi = 0;

				for (int i = 1; i <= n; ++i) {
					if (vi + 1 < (long long)v.v[x][t].size()) {
						vi++;
					}
					else if (wi + 1 < (long long)w.v[1 - t][y].size()) {
						wi++;
					}
					else {
						break;
					}

					if (i >= (long long)r.v[x][y].size()) {
						r.v[x][y].push_back(0);
					}

					long long dab = v.v[x][t][vi] + w.v[1 - t][y][wi];

					while (vi > 0 and wi + 1 < (long long)w.v[1 - t][y].size() and v.v[x][t][vi - 1] + w.v[1 - t][y][wi + 1] > dab) {
						vi--;
						wi++;
						dab = v.v[x][t][vi] + w.v[1 - t][y][wi];
					}

					while (wi > 0 and vi + 1 < (long long)v.v[x][t].size() and v.v[x][t][vi + 1] + w.v[1 - t][y][wi - 1] > dab) {
						vi++, wi--;
						dab = v.v[x][t][vi] + w.v[1 - t][y][wi];
					}

					r.v[x][y][i] = max(r.v[x][y][i], dab);
				}
			}
		}
	}

	return r;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	auto r = rek(0, n);

	// for (int x = 0; x < 2; ++x) {
	// 	for (int y = 0; y < 2; ++y) {
	// 		cout << x << " " << y << endl << "  ";

	// 		for (int i = 0; i < (long long)r.v[x][y].size(); ++i) {
	// 			cout << r.v[x][y][i] << " ";
	// 		}

	// 		cout << endl;
	// 	}
	// }

	for (int i = 1; i <= (n + 1) / 2; ++i) {
		long long ma = 0;

		for (int x = 0; x < 2; ++x) {
			for (int y = 0; y < 2; ++y) {
				if (i < (long long)r.v[x][y].size()) {
					ma = max(ma, r.v[x][y][i]);
				}
			}
		}

		cout << ma << "\n";
	}
}

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