Submission #47886

#	Time	Username	Problem	Language	Result	Execution time	Memory
47886		square1001	Split the sequence (APIO14_sequence)	C++14	50 / 100	2074 ms	2800 KiB

sequence

#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 60;
int n, m, s[100009], p[209][100009]; long long dp[100009], ndp[100009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i + 1];
		s[i + 1] += s[i];
	}
	fill(dp + 1, dp + n + 1, inf);
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			ndp[j] = inf;
			for (int k = 0; k < j; k++) {
				if (ndp[j] > dp[k] - 2LL * s[k] * s[j]) {
					ndp[j] = dp[k] - 2LL * s[k] * s[j];
					p[i][j] = k;
				}
			}
			if(ndp[j] != inf) ndp[j] += 2LL * s[j] * s[j];
		}
		copy(ndp, ndp + n + 1, dp);
	}
	cout << (2LL * s[n] * s[n] - dp[n]) / 2 << '\n';
	int pos = n;
	for (int i = m; i >= 1; i--) {
		pos = p[i][pos];
		cout << pos << (i != 1 ? ' ' : '\n');
	}
	return 0;
}

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