Submission #367396

#	Time	Username	Problem	Language	Result	Execution time	Memory
367396		Bill_00	Split the sequence (APIO14_sequence)	C++14	100 / 100	1598 ms	81588 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];
int p[201][100001];
ll cost(ll x,ll y){
	if(x>y) return 0;
	ll z=sum[y]-sum[x-1];
	return z*z;
}
void fill(int id,ll l1,ll l2,int p1,int p2){
	if(l1>l2){
		return;
	}
	ll lm=l1+l2>>1;
	p[id-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[id-1][lm]=i;
        } 
		if(f[1][lm]>new_cost){
			f[1][lm]=new_cost;
			p[id-1][lm]=i;
		}
	}
	fill(id,l1,lm-1,p1,p[id-1][lm]);
	fill(id,lm+1,l2,p[id-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,i,n,i-1,n);
		for(ll j=1;j<=n;j++){
			f[0][j]=f[1][j];
		}
	}
	int trans=n;
	ll hariu=(sum[n]*sum[n]-f[0][n])/2;
	cout << hariu << "\n";
	for(ll i=k;i>=2;i--){
		ans.pb(p[i-1][trans]);
		trans=p[i-1][trans];
	}
	for(ll i=ans.size()-1;i>=0;i--){
		cout << ans[i] << ' ';
	}
}

Compilation message (stderr)

sequence.cpp: In function 'void fill(int, ll, ll, int, int)':
sequence.cpp:22:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |  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: 29 / 29