Submission #110885

#	Time	Username	Problem	Language	Result	Execution time	Memory
110885		aleksam	Split the sequence (APIO14_sequence)	C++14	100 / 100	973 ms	81016 KiB

sequence

//Apio 14 sequence
#include <bits/stdc++.h>
#define INF INT_MAX
#define MOD 100000007
#define MAX_N 100005
#define MAX_K 205
using namespace std;
 
int mg;
int N, K, a[MAX_N];
long long dpk[MAX_N], dpk1[MAX_N];
int sc[MAX_K][MAX_N];
 
int main(){
	ios::sync_with_stdio(false);
	cin>>N>>K;
	if(N>10000)mg=20;
	else mg=75;
	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];
		dpk[i]=s*s;
		sc[0][i]=N;
	}
	for(int k=1; k<=K; ++k){
		for(int i=0; i<N; ++i)dpk1[i]=dpk[i];
		s=a[N-k-1];
		dpk[N-k-1]=dpk1[N-k]+s*s;
		sc[k][N-k-1]=N-k;
		int scc=N-k;
		
		for(int i=N-k-2; i>=0; --i){
			s+=a[i];
			bool b=0;
			long long sp=0;
			for(int j=1; j<mg; ++j){
				sp+=a[scc-j];
				b=b||(scc>i+j && (s-sp)*(s-sp)+dpk1[scc-j]<=s*s+dpk1[scc]);
				if(b)break;
			}
				//(scc>i+1 && (s-a[scc-1])*(s-a[scc-1])+dp[k-1][scc-1] <= s*s+dp[k-1][scc] )
			while(b){
				scc--;
				s-=a[scc];
				b=0;
				sp=0;
				for(int j=1; j<mg; ++j){
					sp+=a[scc-j];
					b=b||(scc>i+j && (s-sp)*(s-sp)+dpk1[scc-j]<=s*s+dpk1[scc]);
					if(b)break;
				}
			}
			dpk[i]=s*s+dpk1[scc];
			sc[k][i]=scc;
		}
	}
	s=0;
	for(int i=0; i<N; ++i)s+=a[i];
	cout<<(s*s-dpk[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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29