제출 #737824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737824		amirhoseinfar1385	수열 (APIO14_sequence)	C++17	0 / 100	21 ms	16780 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 j=1;j<=k;j++){
		int fj=1;
		for(int i=1;i<=n;i++){
			if(j==1){
				dp[i][j]=ps[i]*suf[i+1];
				dpa[i][j]=-1;
				continue;
			}
			while(fj<i){
				long long now=dp[fj][j-1]+(ps[i]-ps[fj])*suf[i+1];
				long long bad=dp[fj+1][j-1]+(ps[i]-ps[fj+1])*suf[i+1];
				if(bad>now){
					fj++;
				}
				else{
					break;
				}
			}
			//cout<<i<<" "<<j<<" "<<fj<<'\n';
			long long now=dp[fj][j-1]+(ps[i]-ps[fj])*suf[i+1];
			dp[i][j]=now;
			dpa[i][j]=fj;
		}
	}
	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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29