Submission #543411

#	Time	Username	Problem	Language	Result	Execution time	Memory
543411		Sohsoh84	Split the sequence (APIO14_sequence)	C++17	100 / 100	471 ms	84628 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e5 + 10;
const ll INF = 8e18;

int wtf[202][MAXN];
ll dp[2][MAXN], ans, A[MAXN], n, s, tans, k, ptr;
vector<pair<pll, pll>> cht;

inline ll f(pll a, pll b) {
	if (a.X == b.X) return (a.Y <= b.Y ? -INF : INF);
	if (a.X < b.X) swap(a, b);
	return (b.Y - a.Y + (b.Y > a.Y ? (a.X - b.X - 1) : 0)) / (a.X - b.X);
}

inline void add(int ind, ll ml, ll cl) {
	pll a = {ml, cl};
	while (!cht.empty()) {
		ll x = f(cht.back().Y, a);
		if (x <= cht.back().X.X) cht.pop_back();
		else {
			cht.push_back({{x, ind}, a});
			break;
		}
	}

	if (cht.empty())
		cht.push_back({{-INF, ind}, a});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	k++;

	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		tans -= A[i];
	}

	// ans -= sigma C(2, F[i])
	// ans -= F[i] * (F[i] - 1) / 2
	// tans += F[i] * F[i] - F[i]
	
	for (int c = 1; c <= k; c++) {
		int ind = c & 1;
		s = 0;

		cht.clear();
		ptr = 0;
		add(0, 0, 0);
	
		for (int i = 1; i <= n; i++) {
			s += A[i];
			while (ptr < int(cht.size()) - 1 && cht[ptr + 1].X.X <= s) ptr++;
			dp[ind][i] = s * s - (cht[ptr].Y.X * s + cht[ptr].Y.Y);
			wtf[c][i] = cht[ptr].X.Y;
			
			if (c > 1) add(i, 2 * s, -(dp[ind ^ 1][i] + s * s));
		}
	}

	tans += dp[k & 1][n];
	cout << s * (s - 1) / 2 - tans / 2 << endl;

	vector<int> vec;
	int v = n;
	while (k > 1)
		vec.push_back(v = wtf[k--][v]);
	
	reverse(all(vec));
	for (int e : vec)
		cout << e << sep;
	cout << endl;

	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