Submission #235800

#	Time	Username	Problem	Language	Result	Execution time	Memory
235800		eohomegrownapps	Split the sequence (APIO14_sequence)	C++14	100 / 100	1237 ms	90104 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
deque<pair<pair<ll,ll>,ll>> dq;
//{m,c}

ll f(pair<ll,ll> l, ll x){
	return l.first*x+l.second;
}

pair<ll,ll> query(ll x){
	while (dq.size()>1){
		if (f(dq[0].first,x)<f(dq[1].first,x)){
			dq.pop_front();
		} else {
			break;
		}
	}
	return {f(dq[0].first,x),dq[0].second};
}

long double intersect(ll m1, ll c1, ll m2, ll c2){
	return (long double)(c2-c1)/(m1-m2);
}
long double intersect(pair<ll,ll> p1, pair<ll,ll> p2){
	return intersect(p1.first,p1.second,p2.first,p2.second);
}

void addLine(pair<ll,ll> l, ll x){
	ll s = dq.size();
	if (dq[s-1].first.first==l.first){
		if (dq[s-1].first.second<l.second){
			dq.pop_back();
			dq.push_back({l,x});
		}
		return;
	}
	while (dq.size()>1){
		if (intersect(dq[s-1].first,l)<=intersect(dq[s-2].first,l)){
			dq.pop_back();
			s--;
		} else {
			break;
		}
	}
	dq.push_back({l,x});
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll n,kv;
	cin>>n>>kv;
	vector<ll> p(n+1,0);
	for (ll i = 1; i<=n; i++){
		cin>>p[i];
		p[i]+=p[i-1];
	}
	vector<vector<ll>> dp(n,vector<ll>(2,0));
	vector<vector<int>> prev(n,vector<int>(kv+1,-1));
	ll maxval = 0;
	ll maxind = -1;
	for (ll k = 1; k<=kv; k++){
		dq.clear();
		dq.push_back({{0,0},k-1});
		for (ll x = k-1; x<n; x++){
			/*for (auto i : dq){
				cout<<i.first.first<<" "<<i.first.second<<", ";
			}cout<<endl;*/
			auto q = query(p[x]);
			prev[x][k]=q.second;
			dp[x][k%2] = q.first+p[x]*p[n]-p[x]*p[x];
			//cout<<x<<" "<<k<<" "<<dp[x][k]<<endl;
			addLine({p[x],dp[x][(k+1)%2]-p[n]*p[x]},x);
			if (dp[x][k%2]>=maxval){
				maxval=dp[x][k%2];
				maxind=x;
			}
		}
	}
	vector<ll> ans;
	for (ll k = kv; k>=1; k--){
		ans.push_back(maxind);
		//cout<<maxind<<endl;
		maxind=prev[maxind][k];
	}
	cout<<maxval<<'\n';
	for (ll i = ans.size()-1; i>=0; i--){
		cout<<ans[i]<<' ';
	}cout<<'\n';
	return 0;
}

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