Submission #367392

#	Time	Username	Problem	Language	Result	Execution time	Memory
367392		Bill_00	Split the sequence (APIO14_sequence)	C++14	71 / 100	961 ms	131076 KiB

sequence

#include <bits/stdc++.h>
typedef long long ll;
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pp push
using namespace std;
ll sum[100001];
ll f[2][100001];
ll p[2][100001];
vector<ll>l[100001];
ll cost(ll x,ll y){
	if(x>y) return 0;
	ll z=sum[y]-sum[x-1];
	return z*z;
}
void fill(ll l1,ll l2,ll p1,ll p2){
	if(l1>l2){
		return;
	}
	ll lm=l1+l2>>1;
	p[1][lm]=-1;
	f[1][lm]=-1;
	for(ll i=p1;i<=p2;i++){
		if(lm<=i){
			break;
		}
		ll new_cost=f[0][i]+cost(i+1,lm);
      	if(f[1][lm]==-1){
        	f[1][lm]=new_cost;
        	p[1][lm]=i;
        } 
		if(f[1][lm]>new_cost){
			f[1][lm]=new_cost;
			p[1][lm]=i;
		}
	}
	fill(l1,lm-1,p1,p[1][lm]);
	fill(lm+1,l2,p[1][lm],p2);
}
vector<ll>ans;
int main(){
	//int color[200001];
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,k;
	cin >> n >> k;
	k++;
	sum[0]=0;
	for(ll i=1;i<=n;i++){
		ll a;
		cin >> a;
		sum[i]=sum[i-1]+a;
	}
	for(ll i=1;i<=n;i++){
		f[0][i]=sum[i]*sum[i];
		p[0][i]=0;
	}
	for(ll i=2;i<=k;i++){
		fill(i,n,i-1,n);
		for(ll j=1;j<=n;j++){
			f[0][j]=f[1][j];
			p[0][j]=p[1][j];
			l[j].pb(p[1][j]);
		}
	}
	ll trans=n;
	ll hariu=(sum[n]*sum[n]-f[0][n])/2;
	cout << hariu << "\n";
	for(ll i=k;i>=2;i--){
		ans.pb(l[trans][i-2]);
		trans=l[trans][i-2];
	}
	for(ll i=ans.size()-1;i>=0;i--){
		cout << ans[i] << ' ';
	}
}

Compilation message (stderr)

sequence.cpp: In function 'void fill(ll, ll, ll, ll)':
sequence.cpp:23:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  ll lm=l1+l2>>1;
      |        ~~^~~

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