Submission #989391

#	Time	Username	Problem	Language	Result	Execution time	Memory
989391		BuzzyBeez	Split the sequence (APIO14_sequence)	C++17	100 / 100	1069 ms	82928 KiB

sequence

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

const long long inf = 1e18;

long long dp[2][100008];
int par[208][100008];
long long pf[100008], pf_sq[100008];

long long x, y;
long long f(int l, int r) {
	x = pf[r] - pf[l - 1]; y = pf_sq[r] - pf_sq[l - 1];
	return (x * x - y) / 2;
}

void DP(int level, int l, int r, int optl, int optr) {
	if (l > r) return;
	int mid = (l + r) / 2, start = min(mid - 1, optr), optm = 0;
	int cur = (level & 1);
	dp[cur][mid] = inf;
	for (int i = start; i >= optl; --i) {
		if (dp[cur][mid] > dp[cur ^ 1][i] + f(i + 1, mid)) {
			dp[cur][mid] = dp[cur ^ 1][i] + f(i + 1, mid);
			par[level][mid] = optm = i;
		}
	}
	// cout << level << ' ' << mid << ' ' << optl << ' ' << optr << ' ' << optm << ' ' << dp[cur][mid] << "!!\n";
	DP(level, l, mid - 1, optl, optm); DP(level, mid + 1, r, optm, optr);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k; cin >> n >> k; ++k;
	for (int i = 1; i <= n; ++i) {
		cin >> x;
		pf[i] = pf[i - 1] + x;
		pf_sq[i] = pf_sq[i - 1] + x * x;
	}
	for (int i = 1; i <= n; ++i) dp[0][i] = inf;
	for (int i = 1; i <= k; ++i) {
		dp[i & 1][0] = inf; fill(dp[i & 1] + 1, dp[i & 1] + n + 1, 0);
		DP(i, 1, n, 0, n - 1);
	}
	cout << f(1, n) - dp[k & 1][n] << '\n'; int pt = n;
	vector<int> cuts;
	for (int i = k; i > 1; --i) cuts.push_back(par[i][pt]), pt = par[i][pt];
	reverse(cuts.begin(), cuts.end());
	for (int i : cuts) cout << i << ' ';
}

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