제출 #388885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388885		mosiashvililuka	수열 (APIO14_sequence)	C++14	100 / 100	1099 ms	84308 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,dp[100003],dp2[100003],k,jm[100003],f[100009],K1,B1,K2,B2,K3,B3,x,p[100009],pi;
int nxt[100003][202];
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];
		//de.push_back(jm[i],-jm[i]*jm[i]);
	}
	for(i=1; i<=a; i++){
		dp[i]=0;
	}
	for(k=1; k<=b; k++){
		de.clear();I.clear();
		de.push_back(make_pair(jm[k],dp[k]-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;
				}
			}
			dp2[i]=de[0].first*x+de[0].second;
			nxt[i][k]=I.front();
			K3=jm[i];B3=dp[i]-jm[i]*jm[i];
			while(de.size()>=1){
				K1=de.back().first;B1=de.back().second;
				if(K1<=K3&&B1<=B3){
					de.pop_back();
					I.pop_back();
				}else{
					break;
				}
			}
			while(de.size()>=2){
				K2=de[de.size()-1].first;B2=de[de.size()-1].second;
				K1=de[de.size()-2].first;B1=de[de.size()-2].second;
				/*if(K1==K2){
					de.pop_back();
					I.pop_back();
					continue;
				}*/
				if((B2-B3)*(K2-K1)<=(B1-B2)*(K3-K2)){
					de.pop_back();
					I.pop_back();
				}else{
					break;
				}
			}
			if(de.size()>=1){
				K1=de.back().first;B1=de.back().second;
				if(K1==K3){
					continue;
				}
			}
			de.push_back(make_pair(jm[i],dp[i]-jm[i]*jm[i]));
			I.push_back(i);
		}
		for(j=1; j<=a; j++){
			dp[j]=dp2[j];
		}
	}
	cout<<dp[a]<<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: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29