Submission #737825

#	Time	Username	Problem	Language	Result	Execution time	Memory
737825		amirhoseinfar1385	Split the sequence (APIO14_sequence)	C++17	50 / 100	2072 ms	32596 KiB

sequence

    #include<bits/stdc++.h>
    using namespace std;
     
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	int n,k;
    	cin>>n>>k;
    	vector<long long>all(n+1);
    	for(int i=1;i<=n;i++){
    		cin>>all[i];
    	}
    	vector<vector<long long>>dp(n+3,vector<long long>(k+1));
    	vector<vector<long long>>dpa(n+3,vector<long long>(k+1));
    	vector<long long>ps(n+3),suf(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++)
    	{
    		for(int j=0;j<=k;j++){
    			if(j==0){
    				dp[i][j]=0;
    				continue;
    			}
    			if(j==1){
    				dp[i][j]=ps[i]*suf[i+1];
    				dpa[i][j]=-1;
    				continue;
    			}
    			for(int h=1;h<i;h++){
    				long long fake=dp[h][j-1]+(ps[i]-ps[h])*suf[i+1];
    				if(fake>dp[i][j]){
    					dp[i][j]=fake;
    					dpa[i][j]=h;
    				}
    			}
    			if(i>1&&dpa[i][j]<dpa[i-1][j]){
    				assert(0);
    			}
    		}
    	}
    	long long maxa=-1,w=0;
    	for(int i=1;i<=n;i++){
    		if(dp[i][k]>maxa){
    			w=i;
    			maxa=dp[i][k];
    		}	
    	}
    	cout<<maxa<<"\n";
    	int now=k;
    	vector<int>res;
    	while(now>0){
    		res.push_back(w);
    		w=dpa[w][now];
    		now--;
    	}
    	reverse(res.begin(),res.end());
    	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: 0 / 21
• Subtask 6: 0 / 29