Submission #396016

#	Time	Username	Problem	Language	Result	Execution time	Memory
396016		juggernaut	Split the sequence (APIO14_sequence)	C++14	100 / 100	1334 ms	81036 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N=1e5+12;
int n,k,T,IT;
int gr[220][N];
ll pr[N],dp[2][N];
void rec(int tl,int tr,int tpl=1,int tpr=n){
	if(tl>tr)return;
	int tm=(tl+tr)/2,tp=0;
	ll curs=-1;
	for(int i=max(tpl,IT-1);i<=min(tm-1,tpr);i++){
		if(dp[1-T][i]+pr[i]*(pr[tm]-pr[i])>curs)	
			curs=dp[1-T][i]+pr[i]*(pr[tm]-pr[i]),tp=i;	
	}
	dp[T][tm]=curs,gr[IT][tm]=tp;
	rec(tl,tm-1,tpl,tp);
	rec(tm+1,tr,tp,tpr);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    	cin>>pr[i];
    	pr[i]+=pr[i-1];
    }
    k+=1;
    for(int i=2;i<=k;i++){
    	T=i&1,IT=i;
    	rec(1,n);	
    }
    cout << dp[k & 1][n] << "\n";
    for(int j = k, pos = n;j > 1;j--){
    	cout << gr[j][pos] << " ";
    	pos = gr[j][pos];	
    }
}

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