Submission #763957

#	Time	Username	Problem	Language	Result	Execution time	Memory
763957		SanguineChameleon	Holiday (IOI14_holiday)	C++17	24 / 100	5060 ms	13400 KiB

holiday

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

const long long inf = 1e18L + 20;

vector<long long> calc(vector<int> a) {
	int n = a.size();
	vector<long long> res(n * 2 + 1);
	if (n == 0) {
		return res;
	}
	if (n == 1) {
		res[2] = a[0];
		return res;
	}
	vector<int> left(a.begin(), a.begin() + n / 2);
	vector<int> right(a.begin() + n / 2, a.end());
	vector<long long> best_l = calc(left);
	vector<long long> best_r = calc(right);
	for (int i = 0; i <= (n / 2) * 2; i++) {
		res[i] = best_l[i];
	}
	for (int i = 0; i < n / 2; i++) {
		best_l[i] = -inf;
	}
	best_l[n / 2] = 0;
	sort(left.begin(), left.end(), greater<int>());
	for (int i = n / 2 + 1; i <= (n / 2) * 2; i++) {
		best_l[i] = best_l[i - 1] + left[i - n / 2 - 1];
	}
	for (int i = n / 2; i <= (n / 2) * 2; i++) {
		for (int j = 0; j <= (n - n / 2) * 2; j++) {
			res[i + j] = max(res[i + j], best_l[i] + best_r[j]);
		}
	}
	return res;
}

long long solve(int n, int start, int d, int attraction[]) {
	vector<int> left(start * 2);
	for (int i = 0; i < start; i++) {
		left[i * 2] = 0;
		left[i * 2 + 1] = attraction[start - 1 - i];
	}
	vector<int> right(n - 1 - start);
	for (int i = start + 1; i < n; i++) {
		right[i - start - 1] = attraction[i];
	}
	vector<long long> best_l = calc(left);
	vector<long long> best_r = calc(right);
	best_l.resize(d + 1);
	best_r.resize(d + 1);
	for (int i = 1; i <= d; i++) {
		best_l[i] = max(best_l[i], best_l[i - 1]);
		best_r[i] = max(best_r[i], best_r[i - 1]);
	}
	long long res = 0;
	for (int i = 0; i <= d; i++) {
		res = max(res, best_l[i] + best_r[d - i]);
	}
	for (int i = 0; i <= d - 1; i++) {
		res = max(res, best_l[i] + best_r[d - 1 - i] + attraction[start]);
	}
	return res;
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
	long long res1 = solve(n, start, d, attraction);
	for (int i = 0; i < n - 1 - i; i++) {
		swap(attraction[i], attraction[n - 1 - i]);
	}
	start = n - 1 - start;
	long long res2 = solve(n, start, d, attraction);
	return max(res1, res2);
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53