Submission #413938

#	Time	Username	Problem	Language	Result	Execution time	Memory
413938		LastRonin	Split the sequence (APIO14_sequence)	C++14	39 / 100	2074 ms	31924 KiB

sequence

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;

const ll N = 1e4 + 10;

ll n, k;
ll a[N];
ll dp[N][201], pr[N][201];

int main() {
	speed;
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}         
	dp[0][0] = 0;
	for(int j = 1; j <= n; j++) {
	    for(int p = k; p >= 1; p--) {
			for(int i = j; i > p; i--) {
				if(dp[j][p] < dp[i - 1][p - 1] + (a[j] - a[i - 1]) * a[i - 1])
					dp[j][p] = max(dp[j][p], dp[i - 1][p - 1] + (a[j] - a[i - 1]) * a[i - 1]),
					pr[j][p] = i;
			}
		}
 	}
 	cout << dp[n][k] << '\n';
 	vector<ll> vost;
	ll x = n, y = k;
	while(y) {
		x = pr[x][y];
		y--;
		vost.pb(x);
		x--;
 	}
 	reverse(vost.begin(), vost.end());
 	for(auto u : vost)
 		cout << u - 1 << " ";
}
/*
7 3
4 1 3 4 0 2 3
*/

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