Submission #474589

#	Time	Username	Problem	Language	Result	Execution time	Memory
474589		pure_mem	Split the sequence (APIO14_sequence)	C++14	100 / 100	695 ms	83512 KiB

sequence

#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long
#define MP make_pair

using namespace std;

const int N = 1e5 + 123;
const ll INF = 1e18;
typedef pair<ll, ll> Line;

ll f(Line me, ll x) {
	return me.X * x + me.Y;
}

Line cf[N];

int n, k, his[N][202], CHT[N];
ll s[N], dp[N];

bool bad(int x, int y, int z) {
	return (cf[x].Y - cf[y].Y) * 1.0 / (cf[y].X - cf[x].X) >= (cf[x].Y - cf[z].Y) * 1.0 / (cf[z].X - cf[x].X);
}

void solve(int st) {
	CHT[1] = st - 1;
	cf[st - 1] = {s[st - 1], dp[st - 1] - s[st - 1] * s[st - 1]};	
	for(int i = st, l = 1, r = 1;i <= n;i++) {
		while(l < r && f(cf[CHT[l]], s[i]) <= f(cf[CHT[l + 1]], s[i]))
			l++;
		cf[i] = {s[i], dp[i] - s[i] * s[i]};
		dp[i] = f(cf[CHT[l]], s[i]), his[i][st] = CHT[l];
		while(l < r && bad(CHT[r - 1], CHT[r], i))
			r--;
		CHT[++r] = i;
	}
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
		cin >> s[i], s[i] += s[i - 1];
	k += 1;
	for(int i = 2;i <= k;i++) {
		solve(i);
	}
	cout << dp[n] << "\n";
	int pos = n;
	for(int i = k;i >= 2;i--) {
		pos = his[pos][i];
		cout << pos << " ";
	}
}

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