Submission #737864

#	Time	Username	Problem	Language	Result	Execution time	Memory
737864		amirhoseinfar1385	Split the sequence (APIO14_sequence)	C++17	100 / 100	992 ms	84076 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
vector<long long>dp1,dp0;
vector<vector<int>>dpa;
vector<int>ps,suf;
int n,k;
int fj;

void solve(int l,int r,int tl,int tr){
	//cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<fj<<endl;
	if(l>r||tl>tr){
		return ;
	}
	if(tl==tr){
		for(int i=l;i<=r;i++){
			dpa[fj][i]=tl;
		}
		return ;
	}
	int mid=(l+r)>>1;
	int mina=max(tl,dpa[fj-1][mid]);
	int maxa=min(tr,mid-1);
	for(int i=mina;i<=maxa;i++){
		long long fake=dp0[i]+1ll*(ps[mid]-ps[i])*suf[mid+1];
		if(fake>dp1[mid]){
			dp1[mid]=fake;
			dpa[fj][mid]=i;
		}
	}
	solve(l,mid-1,tl,dpa[fj][mid]);
	solve(mid+1,r,dpa[fj][mid],tr);
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	vector<int>all(n+1);
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	dp1.resize(n+3);
	dp0.resize(n+3);
	dpa.resize(k+5,vector<int>(n+3));
	ps.resize(n+3);
	suf.resize(n+3);
	for(int i=1;i<=n;i++){
		ps[i]=ps[i-1]+all[i];
	}
	for(int i=n;i>=1;i--){
		suf[i]=all[i]+suf[i+1];
	}
	for(int i=1;i<=n;i++){
		dp1[i]=1ll*ps[i]*suf[i+1];
		dpa[1][i]=-1;
	}
	for(int j=2;j<=k;j++){
		swap(dp0,dp1);
		for(int i=0;i<=n;i++){
			dp1[i]=0;
		}
		fj=j;
		solve(j,n,1,n);
		for(int i=1;i<j;i++){
			dp1[i]=dp0[i];
			dpa[j][i]=dpa[j-1][i];
		}
		for(int i=j;i<=n;i++){
			dp1[i]=dp0[dpa[j][i]]+1ll*(ps[i]-ps[dpa[j][i]])*suf[i+1];
		}
	}
	long long maxa=-1,w=0;
	for(int i=1;i<n;i++){
		if(dp1[i]>maxa){
			w=i;
			maxa=dp1[i];
		}	
	}
	cout<<maxa<<"\n";
	int now=k;
	vector<int>res;
	vector<int>vis(n+3);
	while(now>0&&w>0){
		//cout<<now<<" "<<w<<endl;
		res.push_back(w);
		vis[w]=1;
		w=dpa[now][w];
		now--;
	}
	reverse(res.begin(),res.end());
	for(int i=1;i<n;i++){
		if(now>0&&vis[i]==0){
			now--;
			res.push_back(i);
		}
	}
	for(auto x:res){
		cout<<x<<" ";
	}
	cout<<endl;
}

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