Submission #69020

#	Time	Username	Problem	Language	Result	Execution time	Memory
69020		FedericoS	Split the sequence (APIO14_sequence)	C++14	50 / 100	2063 ms	132096 KiB

sequence

#include <iostream>
#include <cstring>
using namespace std;
typedef long long int ll;

ll INF=1e18;
int N,K;
ll A[100005];
ll DP[100005][205];
int P[100005][205];
ll res;

int main(){

	cin>>N>>K;
	K++;
	for(int i=0;i<N;i++)
		cin>>A[i];

	for(int k=0;k<K+2;k++)
		for(int i=0;i<N+1;i++)
			DP[i][k]=INF;

	DP[N][0]=0;

	for(int k=1;k<=K;k++)
		for(int i=0;i<N;i++){
			res=0;
			for(int j=i+1;j<=N;j++){
				res+=A[j-1];
				if(DP[j][k-1]+res*res<DP[i][k]){
					DP[i][k]=DP[j][k-1]+res*res;
					P[i][k]=j;
				}
			}
		}


	res=0;
	for(int i=0;i<N;i++)
		res+=A[i];
	cout<<(res*res-DP[0][K])/2<<endl;

	res=P[0][K];
	while(res!=N){
		cout<<res<<" ";
		res=P[res][--K];
	}


}
/*
7 3
4 1 3 4 0 2 3
*/

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