Submission #212747

#	Time	Username	Problem	Language	Result	Execution time	Memory
212747		kig9981	Split the sequence (APIO14_sequence)	C++17	100 / 100	1528 ms	81112 KiB

sequence

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

int PS[100001], P[201][100001];
long long D[2][100001];

void solve(int k, int l, int r, int s, int e)
{
	if (l > r || s > e) return;
	int m = (s + e) >> 1, L = min(m, r);
	D[k & 1][m] = 0x7fffffffffffffffLL;
	for (int i = l; i <= L; i++) {
		if (D[k & 1][m] > D[(k - 1) & 1][i] + 1LL * (PS[m] - PS[i])*(PS[m] - PS[i])) {
			D[k & 1][m] = D[(k - 1) & 1][i] + 1LL * (PS[m] - PS[i])*(PS[m] - PS[i]);
			P[k][m] = i;
		}
	}
	solve(k, l, P[k][m], s, m - 1);
	solve(k, P[k][m], r, m + 1, e);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> PS[i];
		PS[i] += PS[i - 1];
		D[0][i] = 1LL * PS[i] * PS[i];
	}
	for (int i = 1; i <= K; i++) {
		solve(i, i, N, i, N);
	}
	cout << (1LL * PS[N] * PS[N] - D[K & 1][N]) / 2 << '\n';
	for (; K; K--) {
		cout << P[K][N] << ' ';
		N = P[K][N];
	}
	return 0;
}

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