Submission #101648

#	Time	Username	Problem	Language	Result	Execution time	Memory
101648		KCSC	Split the sequence (APIO14_sequence)	C++14	100 / 100	1585 ms	81020 KiB

sequence

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

const int KMAX = 205;
const int NMAX = 100005;

long long dp[2][NMAX], psm[NMAX];
int fth[KMAX][NMAX];

void divide(int p, int le, int ri, int st, int en) {
	if (le > ri) {
		return; }
	int md = (le + ri) / 2, l = p & 1; 
	dp[l][md] = -1;
	for (int i = st; i <= md - 1 and i <= en; ++i) {
		if (dp[l][md] < dp[l ^ 1][i] + psm[i] * (psm[md] - psm[i])) {
			dp[l][md] = dp[l ^ 1][i] + psm[i] * (psm[md] - psm[i]); 
			fth[p][md] = i; } }
	divide(p, le, md - 1, st, fth[p][md]);
	divide(p, md + 1, ri, fth[p][md], en); }

int main(void) {
#ifdef HOME
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
#endif
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> psm[i]; psm[i] += psm[i - 1]; }
	for (int i = 1; i <= k; ++i) {
		divide(i, i + 1, n, i, n); }
	cout << dp[k & 1][n] << endl;
	for (int i = k, j = n; i >= 1; --i) {
		cout << fth[i][j] << " "; j = fth[i][j]; }
	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