Submission #570614

#	Time	Username	Problem	Language	Result	Execution time	Memory
570614		beaconmc	Split the sequence (APIO14_sequence)	C++14	100 / 100	649 ms	83152 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--)
#define double long double


using namespace std;

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



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

bool case1(ll a, ll b, ll i){
	return (dp[a][0] - dp[b][0]) <= (suff[b] - suff[a])*suff[i];
}


bool case2(ll a, ll b, ll i){
	return (dp[a][0] - dp[b][0]) * (suff[i] - suff[b]) <= (dp[b][0] - dp[i][0]) * (suff[b] - 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];
	}



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

	
	
	FOR(j,1,k+2){

		deque<ll> q;
		q.push_back(0);

		FOR(i,1,n+1){

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

			while (q.size() >= 2 && case1(q[0], q[1], i)){
				q.pop_front();
			}



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

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


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

			q.push_back(i);
		}

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


	}



	cout << dp[n][1] << "\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: 29 / 29