Submission #570605

#	Time	Username	Problem	Language	Result	Execution time	Memory
570605		beaconmc	Split the sequence (APIO14_sequence)	C++14	71 / 100	929 ms	83760 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

ll dp[100002][2];
int ans[100002][202];
ll suff[100002];



double slope(ll a, ll b, ll j){
	if (j==0) j=2;
	if (suff[b] == suff[a]){
		if ((double)dp[a][j-1] - (double)dp[b][j-1] <= 0) return 1000000000000;
	}
	return ((double)dp[a][j-1] - (double)dp[b][j-1]) / ((double)suff[b] - (double)suff[a]);
}


int main(){

	ll n,k;
	cin >> n >> k;


	

	vector<ll> nums(n);
	FOR(i,0,n) cin >> nums[i];

	suff[n] = 0;
	suff[n-1] = nums[n-1];
	FORNEG(i,n-2,-1){
		suff[i] = suff[i+1] + nums[i];
	}



	dp[0][0] = 0;
	
	
	FOR(j,1,k+2){
		ll sus = j;
		j = j%2;
		deque<ll> q;
		q.push_back(0);
		dp[0][j] = 0;
		FOR(i,1,n+1){

			//cout << q[0] << " " << q[1] << " " << slope(q[0], q[1], j) << " " << suff[i] << endl;

			while (q.size() >= 2 && slope(q[0], q[1], j) >= suff[i]){
				q.pop_front();
			}
			ll realsus;
			if (j==0) realsus = 1;
			else realsus = 0;


			ll tmp = q.front();
			dp[i][j] = dp[tmp][realsus] + (suff[tmp]-suff[i])*suff[i];
			ans[i][sus] = tmp;

			//cout << tmp << " " << maxpos << endl;
			//cout << endl;


			while (q.size() >=2 && slope(q[q.size()-2], q[q.size()-1], j) < slope(q[q.size()-1], i, j)){
				q.pop_back();
			}

			q.push_back(i);

		}
		j = sus;

	}
	ll maxi = -1;

	FOR(i,0,n+1){
		FOR(j,0,2){
			maxi = max(maxi, dp[n][j]);
		}
	}

	cout << maxi << "\n";

	// FOR(i,0,n+1){
	// 	FOR(j,0,k+2){
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	ll sus = n;
	vector<ll> sussy;


	FOR(i,0,k){
		sus = ans[sus][k-i+1];
		cout << sus << " ";
	}




}

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