Submission #1169896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169896		PieArmy	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	584 KiB

sequence

#include<bits/stdc++.h>
typedef __int128_t ll;
using namespace std;
#define int ll
int32_t n,k;
int32_t arr[100023];
ll pref[100023],suf[100023];
deque<pair<int,ll>>q[200];
ll dp[200];
int opt[100023][200];

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		pref[i]=arr[i]+pref[i-1];
	}
	for(int i=n;i>=1;i--){
		suf[i]=suf[i+1]+arr[i];
	}
	q[k-1].push_back({0,0});
	ll ans=-1;
	for(int i=1;i<n;i++){
		for(int j=0;j<k;j++){
			opt[i][j]=opt[i-1][j];
			while(q[j].size()>1){
				if(q[j][0].second-suf[i+1]*pref[q[j][0].first]<=q[j][1].second-suf[i+1]*pref[q[j][1].first])q[j].pop_front();
				else break;
			}
			if(q[j].size()){
				if(dp[j]<q[j][0].second+suf[i+1]*(pref[i]-pref[q[j][0].first])){
					opt[i][j]=q[j][0].first;
					dp[j]=q[j][0].second+suf[i+1]*(pref[i]-pref[q[j][0].first]);
				}
			}
			//cout<<opt[i][j]<<":"<<dp[j]<<" ";
			if(j==0){
				if(dp[j]>ans){
					ans=dp[j];
					opt[n][0]=i;
				}
				continue;
			}
			pair<int,ll>p={i,dp[j]};
			while(q[j-1].size()>1){
				pair<int,ll>a=q[j-1].front();q[j-1].pop_front();
				if(__int128_t(q[j-1].back().second-p.second)*__int128_t(pref[a.first]-pref[q[j-1].back().first])<__int128_t(q[j-1].back().second-a.second)*__int128_t(pref[p.first]-pref[q[j-1].back().first]))continue;
				q[j-1].push_back(a);
				break;
			}
			bool ch=true;
			while(q[j-1].size()){
				if(pref[q[j-1].back().first]==pref[p.first]){
					if(q[j-1].back().second<=p.second)q[j-1].pop_back();
					else{
						ch=false;
						break;
					}
				}
				else break;
			}
			if(ch)q[j-1].push_back(p);
		}
		/*cout<<endl;
			if(i==n){
				for(int j=0;j<k;j++){
					for(auto x:q[j])cout<<x.first<<" ";
					cout<<endl;
				}
			}*/
	}
	vector<int>v;
	int pos=opt[n][0];
	cout<<int32_t(ans)<<endl;
	for(int i=0;i<k;i++){
		v.push_back(pos);
		pos=opt[pos][i];
	}
	while(v.size()){
		cout<<int32_t(v.back())<<" ";
		v.pop_back();
	}
}

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