Submission #503538

#	Time	Username	Problem	Language	Result	Execution time	Memory
503538		mosiashvililuka	Split the sequence (APIO14_sequence)	C++14	100 / 100	967 ms	84548 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,k,K,B,dp[100009],dp2[100009],f[100009],jm[100009],X;
deque <pair <pair <long long, long long>, long long> > de;
int DP[100003][203];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>k;k++;
	for(i=1; i<=a; i++){
		cin>>f[i];jm[i]=jm[i-1]+f[i];
	}
	for(j=2; j<=k; j++){
		while(de.size()) de.pop_back();
		for(i=j; i<=a; i++){
			K=jm[i-1];B=dp[i-1]-jm[i-1]*jm[i-1];
			while(de.size()){
				if(de[de.size()-1].first.second<=B){
					de.pop_back();
				}else{
					break;
				}
			}
			while(de.size()>1){
				zx=(B-de[de.size()-2].first.second)*(de[de.size()-2].first.first-de[de.size()-1].first.first);
				xc=(de[de.size()-1].first.second-de[de.size()-2].first.second)*(de[de.size()-2].first.first-K);
				if(zx>xc){
					break;
				}
				de.pop_back();
			}
			de.push_back({{K,B},i-1});
			
			X=jm[i];
			while(de.size()>1){
				zx=de[0].first.first*X+de[0].first.second;
				xc=de[1].first.first*X+de[1].first.second;
				if(zx<=xc){
					de.pop_front();
				}else{
					break;
				}
			}
			dp2[i]=de[0].first.first*X+de[0].first.second;
			DP[i][j]=de[0].second;
		}
		
		for(i=1; i<=a; i++){
			dp[i]=dp2[i];dp2[i]=0;
		}
	}
	cout<<dp[a]<<"\n";
	i=a;j=k;
	while(j>1){
		i=DP[i][j];j--;
		cout<<i<<" ";
	}
	return 0;
}

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