Submission #853613

#	Time	Username	Problem	Language	Result	Execution time	Memory
853613		serifefedartar	Split the sequence (APIO14_sequence)	C++17	100 / 100	670 ms	87588 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;
 
struct Line {
	ll m, c;
	Line(ll M, ll C) : m(M), c(C) { }
	ll operator() (ll x) {
		return m * x + c;
	}
};
 
double intersect(Line a, Line b) {
	if (a.m == b.m) {
		if (a.c == b.c)
			return (double)-1e9;
		return (double)1e9; 
	}
	return (double)(b.c - a.c) / (a.m - b.m);
}
 
deque<pair<pair<Line,double>,int>> lines;
void addLine(Line newLine, int x) {
	while (lines.size() > 1 && lines.back().f.s >= intersect(lines.back().f.f, newLine))
		lines.pop_back();
 
	if (lines.empty())
		lines.push_back({{newLine, 0.0}, x});
	else
		lines.push_back({{newLine, intersect(lines.back().f.f, newLine)}, x});
}
 
pair<ll,int> query(ll x) {
	if (lines.size() == 0)
		return {0, -1};
	while (lines.size() > 1) {
		if (lines[1].f.s <= (double)x)
			lines.pop_front();
		else
			break;
	}
	return {lines[0].f.f(x), lines[0].s};
}
 
vector<ll> A;
ll dp[2][MAXN], pref[MAXN];
int opt[205][MAXN];
int main() {
	fast
	memset(opt, -1, sizeof(opt)); 
	int n, k;
	cin >> n >> k;
 
	A = vector<ll>(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		pref[i] = pref[i-1] + A[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[0][i] = pref[i] * (pref[n] - pref[i]);
		opt[1][i] = i;
	}
 
	for (int K = 2; K <= k; K++) {
		int from = K % 2;
		int to = 1 - K % 2;
		lines.clear();
 
		for (int i = 1; i <= n; i++) {
			ll x = pref[i] - pref[n];
			ll Q = query(x).f;
			ll plc = query(x).s;
			dp[to][i] = Q + pref[i] * (pref[n] - pref[i]);
			opt[K][i] = plc;
			addLine(Line(pref[i], dp[from][i]), i);
		}
	}
 
	lines.clear();
	for (int i = 1; i <= n-1; i++)
		addLine(Line(pref[i], dp[1 - k%2][i]), i);
	ll Q = query(0).f;
	ll plc = query(0).s;
	dp[k%2][n] = Q;
	opt[k+1][n] = plc;
 
 
	cout << dp[k%2][n] << "\n";
	int now_k = k+1;
	int now_plc = n;
	while (now_k > 1) {
		now_plc = opt[now_k][now_plc];
		now_k--;
		
		if (now_plc == -1)
			cout << "1 ";
		else
			cout << now_plc << " ";
	}
	cout << "\n";
}

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