Submission #409807

#	Time	Username	Problem	Language	Result	Execution time	Memory
409807		nicholask	Split the sequence (APIO14_sequence)	C++14	50 / 100	2081 ms	31948 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
signed main(){
	int n,k;
	cin>>n>>k;
	int a[n+1];
	for (int i=1; i<=n; i++) cin>>a[i];
	int ps[n+1];
	for (int i=0; i<=n; i++){
		if (!i) ps[i]=0;
		else ps[i]=ps[i-1]+a[i];
	}
	pair <int,int> dp[n+1][k+1];
	for (int i=0; i<=n; i++){
		for (int j=0; j<=k; j++) dp[i][j]={-1e18,-1e18};
	}
	for (int i=1; i<=n-1; i++) dp[i][1]={ps[i]*(ps[n]-ps[i]),i};
	for (int j=2; j<=k; j++){
		for (int i=1; i<=n; i++){
			for (int l=1; l<i; l++){
				pair <int,int> tp={dp[l][j-1].x+(ps[i]-ps[l])*(ps[n]-ps[i]),l};
				dp[i][j]=max(dp[i][j],tp);
			}
		}
	}
	int ma=-1e18,wh=1;
	for (int i=1; i<n; i++){
		if (dp[i][k].x>ma){
			ma=dp[i][k].x;
			wh=i;
		}
	}
	cout<<ma<<endl;
	vector <int> ans;
	ans.pb(wh);
	for (int i=k; i>1; i--){
		wh=dp[wh][i].y;
		ans.pb(wh);
	}
	reverse(ans.begin(),ans.end());
	for (auto&i:ans) cout<<i<<' ';
}

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