Submission #408918

#	Time	Username	Problem	Language	Result	Execution time	Memory
408918		penguinhacker	Split the sequence (APIO14_sequence)	C++14	100 / 100	1243 ms	81988 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, k, a[mxN], last[mxN][201];
ll p[mxN+1], dp[mxN], dp2[mxN];

// p[i+1]x + dp[i] - p[i+1]*p[n]

double ix(int i, int j) {
	ll a=p[i+1], b=dp[i]-p[i+1]*p[n];
	ll c=p[j+1], d=dp[j]-p[j+1]*p[n];
	return (double)(b-d)/(c-a);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=0; i<n; ++i) {
		cin >> a[i];
		p[i+1]=p[i]+a[i];
	}
	for (int i=0; i<n; ++i) {
		dp[i]=p[i+1]*(p[n]-p[i+1]);
		last[i][0]=-1;
	}
	for (int i=1; i<=k; ++i) {
		deque<int> dq;
		auto Add=[&](int j) {
			if (dq.size()&&!a[j])
				return;
			while(dq.size()>=2&&ix(dq.end()[-2], j)<ix(dq.end()[-2], dq.back()))
				dq.pop_back();
			dq.push_back(j);
		};
		memcpy(dp2, dp, sizeof(dp));
		//for (int j=0; j<i; ++j)
		Add(i-1);
		for (int j=i; j<n; ++j) {
			while(dq.size()>=2&&ix(dq[0], dq[1])<p[j+1])
				dq.pop_front();
			dp2[j]=p[j+1]*(p[n]-p[j+1])+p[j+1]*p[dq[0]+1]+dp[dq[0]]-p[dq[0]+1]*p[n];
			last[j][i]=dq[0];
			//cout << i << " " << j << " " << dq[0] << "\n";
			Add(j);
		}
		memcpy(dp, dp2, sizeof(dp));
	}
	cout << dp[n-1] << "\n";
	vector<int> ans(k);
	for (int i=k, c=n-1; i; --i) {
		c=last[c][i];
		ans[i-1]=c;
	}
	for (int i : ans)
		cout << i+1 << " ";
	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