Submission #1180944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180944		boclobanchat	Split the sequence (APIO14_sequence)	C++20	100 / 100	994 ms	89680 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const long long INF=1e18;
long long dp[MAXN][2],pref[MAXN];
int trace[MAXN][222];
void dnc(int l,int r,int pl,int pr,int c)
{
	if(l>r) return ;
	int pos=0,mid=(l+r)/2;
	for(int i=pl;i<=pr&&i<=mid;i++) if(dp[mid][c%2]<dp[i-1][1-c%2]+pref[i-1]*(pref[mid]-pref[i-1]))
		dp[mid][c%2]=dp[i-1][1-c%2]+pref[i-1]*(pref[mid]-pref[i-1]),pos=i;
	trace[mid][c]=pos-1;
	if(l==r) return ;
	dnc(l,mid-1,pl,pos,c);
	dnc(mid+1,r,pos,pr,c);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
    	int res;
    	cin>>res;
    	pref[i]=pref[i-1]+res;
	}
	for(int i=0;i<=n;i++) dp[i][0]=dp[i][1]=-INF;
	dp[0][0]=0;
	for(int i=1;i<=k+1;i++)
	{
		for(int j=1;j<=n;j++) dp[j][i%2]=-INF;
		dnc(i,n,i-1,n,i);
	}
	cout<<dp[n][1-k%2]<<"\n";
	int pos=n;
	for(int i=k+1;i>1;i--) cout<<(pos=trace[pos][i])<<" ";
}

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