Submission #213227

#	Time	Username	Problem	Language	Result	Execution time	Memory
213227		someone_aa	Split the sequence (APIO14_sequence)	C++17	50 / 100	194 ms	3840 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const ll inf = 1e10;
const int maxn = 1100;
ll arr[maxn], pref[maxn];
ll dp[maxn][210], n, k;
ll parent[maxn][210];

ll getsum(int l, int r) {
	if(r < l) return 0;
	return pref[r] - pref[l-1];
}

int main() {
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin>>arr[i];
		pref[i] = pref[i-1] + arr[i];
	}

	for(int i=1;i<n;i++) {
		dp[i][1] = pref[i] * getsum(i+1, n);
	}

	ll result = -inf;
	int resultind = -1;
	for(int d=2;d<=k;d++) {
		for(int i=d;i<n;i++) {
			dp[i][d] = -inf;
			for(int j=d-1;j<i;j++) {
				if(dp[j][d-1] + getsum(j+1, i) * getsum(i+1, n) >= dp[i][d]) {
					dp[i][d] = dp[j][d-1] + getsum(j+1, i) * getsum(i+1, n);
					parent[i][d] = j;
				}
			}
		}
	}

	for(int i=1;i<n;i++) {
		if(dp[i][k] >= result) {
			result = dp[i][k];
			resultind = i;
		}
	}

	vector<int>v;
	cout<<result<<"\n";
	for(int i=k;i>=1;i--) {
		v.pb(resultind);
		resultind = parent[resultind][i];
	}
	reverse(v.begin(), v.end());
	for(int i:v) 
		cout<<i<<" ";
	cout<<"\n";
}

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