Submission #399155

#	Time	Username	Problem	Language	Result	Execution time	Memory
399155		BERNARB01	Split the sequence (APIO14_sequence)	C++17	22 / 100	2102 ms	95556 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = 201;

int n, a[N];
pair<int, int> to[N][N][N];
long long dp[N][N][N], s[N];
vector<int> ans;

long long sol(int l, int r, int k) {
	if (l == r || k == 0) {
		return 0;
	}
	long long& ret = dp[l][r][k];
	if (ret != -1) {
		return ret;
	}
	ret = 0;
	long long sl = (l ? s[l - 1] : 0);
	for (int i = l; i < r; i++) {
		for (int j = 0; j < k; j++) {
			long long sub = (s[i] - sl) * (s[r] - s[i]) + sol(l, i, j) + sol(i + 1, r, k - 1 - j);
			if (sub > ret) {
				ret = sub;
				to[l][r][k] = {i, j};
			}
		}
	}
	return ret;
}

void bld(int l, int r, int k) {
	if (l == r || k == 0) {
		return;
	}
	//cout << l << " " << r << " " << k << '\n';
	pair<int, int> p = to[l][r][k];
	ans.push_back(p.first);
	bld(l, p.first, p.second);
	bld(p.first + 1, r, k - 1 - p.second);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(dp, -1, sizeof dp);
	int k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		s[i] = a[i] + (i ? s[i - 1] : 0);
	}
	cout << sol(0, n - 1, k) << '\n';
	bld(0, n - 1, k);
	for (const auto& x : ans) {
		cout << x + 1 << " ";
	}
	cout << '\n';
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29