Submission #69027

#	Time	Username	Problem	Language	Result	Execution time	Memory
69027		FedericoS	Split the sequence (APIO14_sequence)	C++14	50 / 100	1557 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;
ll M;
ll S;
int R1[100005],R2[100005];
ll e=1000;

int main(){

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

	for(int i=0;i<N;i++)
		M+=A[i];
	M=M/K;

	for(ll i=0;i<K+1;i++){
		while(S<i*M and res<N)
			S+=A[res++];
		if(i)
			R2[K+1-i]=res+e;
		R1[K-i]=res-e;
	}
	R2[0]=N;

	/*for(int i=0;i<=K;i++)
		cout<<i<<" "<<R1[i]<<" "<<R2[i]<<endl;
	return 0;*/


	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=max(0,R1[k]);i<min(N,R2[k]);i++){
			res=0;
			for(int j=i+1;j<=min(N,R2[k-1]);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