Submission #981788

#	Time	Username	Problem	Language	Result	Execution time	Memory
981788		Halym2007	Split the sequence (APIO14_sequence)	C++17	100 / 100	713 ms	84060 KiB

sequence

/*
I solved this problem with Convex hull trick
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define ll long long
#define sz size()
#define pb push_back
ll p[N], a[N], n, k, dp[N];
int par[N][205];
//CHT means convex hull trick
struct CHT {
	ll m, c;
	int idx;
	ll get (ll x) {	
		return m * x + c;
	}
	long double intersect (CHT x) {
		return (long double)(x.c - c) / (long double)(m - x.m);
	}
};

int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
	for (int i = 1; i <= k; ++i) {
		deque <CHT> d;
		d.pb ({p[i], dp[i] - p[i] * p[i], i});
		for (int j = i + 1; j <= n; ++j) {
			while ((int)d.sz >= 2 and d[0].get (p[j]) <= d[1].get (p[j])) d.pop_front();
			ll aa = d[0].get (p[j]);
			CHT tr = {p[j], dp[j] - p[j] * p[j],  j};
			par[j][i] = d[0].idx;
			while ((int)d.sz >= 2 and tr.intersect(d[(int)d.sz - 2]) <= d.back().intersect(d[(int)d.sz - 2])) d.pop_back();
			d.pb (tr);
			dp[j] = aa;
		}
		
	}
	cout << dp[n] << "\n";
	int idx = par[n][k];
	int val = k;
	while (idx) {
		val--;
		cout << idx << " ";
		idx = par[idx][val];
	}
}

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