Submission #388735

#	Time	Username	Problem	Language	Result	Execution time	Memory
388735		mosiashvililuka	Split the sequence (APIO14_sequence)	C++14	33 / 100	81 ms	131076 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,dp[100003][202],k,jm[100003],f[100009],K1,B1,K2,B2,x,nxt[100003][202],p[100009],pi;
deque <pair <long long, long long> > de;
deque <long long> I;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=a; i++){
		cin>>f[i];
		jm[i]=jm[i-1]+f[i];
	}
	for(i=1; i<=a; i++){
		dp[i][0]=0;
	}
	for(k=1; k<=b; k++){
		de.clear();I.clear();
		de.push_back(make_pair(jm[k],dp[k][k-1]-jm[k]*jm[k]));
		I.push_back(k);
		for(i=k+1; i<=a; i++){
			x=jm[i];
			while(de.size()>=2){
				K1=de[0].first;B1=de[0].second;
				K2=de[1].first;B2=de[1].second;
				if(K2*x+B2>=K1*x+B1){
					de.pop_front();
					I.pop_front();
				}else{
					break;
				}
			}
			dp[i][k]=de[0].first*x+de[0].second;
			nxt[i][k]=I.front();
			de.push_back(make_pair(jm[i],dp[i][k-1]-jm[i]*jm[i]));
			I.push_back(i);
		}
	}
	cout<<dp[a][b]<<endl;
	pi=0;
	c=a;
	for(j=b; j>=1; j--){
		c=nxt[c][j];
		pi++;
		p[pi]=c;
	}
	for(i=pi; i>=1; i--) cout<<p[i]<<" ";
	return 0;
}

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