Submission #367389

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

sequence

#include <bits/stdc++.h>
typedef long long ll;
const ll inf=9000000000000000000;
#define fr(i,c,d) for(ll i=c;i<=d;i++)
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pp push
using namespace std;
//int h[200001],p[200001];
//int sum[100001];
//pair<ll,ll>p[100001];
//pair<ll,ll>p1[100001];
//string s;
const ll sz=173;
string str(string x,int l,int r){
	string h;
	for(int i=l;i<=r;i++){
		h+=x[i];
	}
	return h;
}
ll sum[100001];
ll f[201][100001];
ll p[201][100001];
ll cost(int x,int y){
	if(x>y) return 0;
	ll z=sum[y]-sum[x-1];
	return z*z;
}
void fill(ll k,ll l1,ll l2,ll p1,ll p2){
	if(l1>l2){
		return;
	}
	ll lm=l1+l2>>1;
	p[k][lm]=-1;
	f[k][lm]=-1;
	for(ll i=p1;i<=p2;i++){
		if(lm<=i){
			break;
		}
		ll new_cost=f[k-1][i]+cost(i+1,lm);
      	if(f[k][lm]==-1){
        	f[k][lm]=new_cost;
        	p[k][lm]=i;
        } 
		if(f[k][lm]>new_cost){
			f[k][lm]=new_cost;
			p[k][lm]=i;
		}
	}
	//cout <<f[k][lm] << ' ' << k << ' ' << lm << endl;
	fill(k,l1,lm-1,p1,p[k][lm]);
	fill(k,lm+1,l2,p[k][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[1][i]=sum[i]*sum[i];
		//cout << f[1][i] << endl;
		p[1][i]=0;
	}
	for(ll i=2;i<=k;i++){
		fill(i,i,n,i-1,n);
	}
	ll trans=n;
	ll hariu=(sum[n]*sum[n]-f[k][n])/2;
	cout << hariu << "\n";
	for(ll i=k;i>=2;i--){
		ans.pb(p[i][trans]);
		trans=p[i][trans];
	}
	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, ll)':
sequence.cpp:37:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  ll lm=l1+l2>>1;
      |        ~~^~~

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