Submission #161920

#	Time	Username	Problem	Language	Result	Execution time	Memory
161920		HungAnhGoldIBO2020	Split the sequence (APIO14_sequence)	C++14	100 / 100	1378 ms	81440 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
const int K=201;
int n,pre[K][N];
long long dp[2][N],sum[N];
stack<int> lis;
void solve(int idx,int l,int r,int lef,int rig){
	if(lef>rig){
		return;
	}
	int i,mid=(lef+rig)>>1;
	long long max1=-1;
	for(i=min(mid-1,r);i>=l;i--){
		if(max1<dp[(idx+1)&1][i]+(sum[mid]-sum[i])*(sum[n]-sum[mid])){
			max1=dp[(idx+1)&1][i]+(sum[mid]-sum[i])*(sum[n]-sum[mid]);
			pre[idx][mid]=i;
		}
	}
	dp[idx&1][mid]=max1;
	solve(idx,l,pre[idx][mid],lef,mid-1);
	solve(idx,pre[idx][mid],r,mid+1,rig);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,num;
	cin>>n>>num;
	for(i=1;i<=n;i++){
		cin>>j;
		sum[i]=sum[i-1]+j;
	}
	for(i=1;i<=n;i++){
		dp[1][i]=(sum[n]-sum[i])*sum[i];
		pre[1][i]=i;
	}
	for(i=2;i<=num;i++){
		solve(i,i-1,n-1,i,n-1);
	}
	j=n-1;
	for(i=num;i<n;i++){
		if(dp[num&1][j]<dp[num&1][i]){
			j=i;
		}
	}
	cout<<dp[num&1][j]<<'\n';
	for(i=num;i>0;i--){
		lis.push(j);
		j=pre[i][j];
	}
	while(lis.size()){
		cout<<lis.top()<<' ';
		lis.pop();
	}
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:27:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,num;
          ^

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