Submission #238147

#	Time	Username	Problem	Language	Result	Execution time	Memory
238147		super_j6	Split the sequence (APIO14_sequence)	C++14	11 / 100	23 ms	6784 KiB

sequence

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<ll, ll>
#define f first
#define s second

const int maxn = 100001, maxk = 202;
int n, k;
int p[maxk][maxn];
pi l[maxk][maxn];
int s[maxk], e[maxk];
ll c;
int ans[maxn];

bool cp(pi x, pi y, pi z){
	return (x.f - z.f) * (y.s - x.s) >= (x.f - y.f) * (z.s - x.s);
}

ll f(ll x, ll y, ll z){
	return l[x][y].f * z + l[x][y].s;	
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	k++;
	
	l[0][0] = {0, 0};
	for(int i = 1; i <= k; i++) l[i][0] = {0, 100000000000000};
	for(int i = 0; i < n; i++){
		ll x;
		cin >> x;
		c += x;
		for(int j = k; j; j--){
			while(e[j - 1] - s[j - 1] > 1 && f(j - 1, s[j - 1], c) >= f(j - 1, s[j - 1] + 1, c)) s[j - 1]++;
			pi x = {-2 * c, 2 * c * c + f(j - 1, p[j][i] = s[j - 1], c)};
			while(e[j] - s[j] > 2 && cp(l[j][e[j] - 2], l[j][e[j] - 1], x)) e[j]--;
			l[j][e[j]++] = x;
		}
	}
	
	for(int i = k - 2, j = p[k][n - 1]; ~i; j = p[i-- + 1][j]) ans[i] = j + 1;
	
	cout << ((2 * c * c - l[k][e[k] - 1].s) / 2) << endl;
	cout << ans[0];
	for(int i = 1; i < k - 1; i++) cout << " " << ans[i];
	cout << endl;
	

	return 0;
}

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