Submission #110870

#	Time	Username	Problem	Language	Result	Execution time	Memory
110870		aleksam	Split the sequence (APIO14_sequence)	C++14	0 / 100	2066 ms	25992 KiB

sequence

//Apio 14 sequence
#include <bits/stdc++.h>
#define INF LLONG_MAX
#define MOD 100000007
#define MAX_N 100005
#define MAX_K 205
using namespace std;

int N, K, a[MAX_N];
long long dp[MAX_K][MAX_N];
int sc[MAX_K][MAX_N];

int main(){
	ios::sync_with_stdio(false);
	cin>>N>>K;
	for(int i=0; i<N; ++i){
		cin>>a[i];
	}
	long long s=0;
	for(int i=N-1; i>=0; --i){
		s+=a[i];
		dp[0][i]=s*s;
		sc[0][i]=N;
	}
	for(int k=1; k<=K; ++k){
		for(int i=N-k-1; i>=0; --i){
			s=0;
			long long min=INF;
			
			int argmin=-1;
			assert(i<sc[k-1][i]);
			for(int j=i; j<sc[k-1][i]; ++j){
				s+=a[j];
				if(min>s*s+dp[k-1][j+1]){
					min=s*s+dp[k-1][j+1];
					argmin=j+1;
				}	
			}
			dp[k][i]=min;
			sc[k][i]=argmin;
		}
	}
	s=0;
	for(int i=0; i<N; ++i)s+=a[i];
	cout<<(s*s-dp[K][0])/2<<endl;
	int cur=0;
	for(int i=0; i<K; ++i){
		cout<<sc[K-i][cur]<<" ";
		cur=sc[K-i][cur];
	}
	return 0;
}

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

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