Submission #241096

#	Time	Username	Problem	Language	Result	Execution time	Memory
241096		vioalbert	Split the sequence (APIO14_sequence)	C++14	100 / 100	1943 ms	83884 KiB

sequence

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

const ll N = 1e5+5, K = 205;
ll n, k;
ll a[N], pref[N];
ll dp[N][2];
int opt[N][K];

ll cost(int i, int j) {
	return (pref[j] - pref[i-1]) * (pref[n] - pref[j]);
}

void solve(int j, int l, int r, int optL, int optR) {
	if(l > r) return;
	int i = (l+r)/2;
	for(int k = optL; k <= min(i-1, optR); k++) {
		ll cur = dp[k][(j-1)&1] + cost(k, i-1);
		if(dp[i][j&1] <= cur)
			dp[i][j&1] = cur, opt[i][j] = k;
	}

	solve(j, l, i-1, optL, opt[i][j]);
	solve(j, i+1, r, opt[i][j], optR);
}

void solve() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	pref[0] = 0;
	for(int i = 1; i <= n; i++) {
		dp[i][0] = 0;
		opt[i][0] = 0;
		pref[i] = pref[i-1] + a[i];
	}

	for(int j = 1; j <= k; j++) {
		for(int i = 1; i <= n; i++)
			dp[i][j&1] = -1;
		solve(j, 1, n, j, n-1);
	}

	ll ans = -1; int cur = -1;
	for(int i = 1; i <= n; i++) {
		if(ans < dp[i][k&1])
			ans = dp[i][k&1], cur = i;
	}
	cout << ans << '\n';
	for(int i = k; i > 0; i--) {
		cout << cur-1 << ' ';
		cur = opt[cur][i];
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
	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