Submission #34826

#	Time	Username	Problem	Language	Result	Execution time	Memory
34826		cheater2k	Split the sequence (APIO14_sequence)	C++14	71 / 100	2000 ms	89248 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

struct line {
	long long a; long long b; int id;
	line(long long a=0, long long b=0, int id=0): a(a), b(b), id(id) {}
};

bool bad(line l1, line l2, line l3) {
	double X13 = (double)(l1.b - l3.b) / (l3.a - l1.a);
	double X12 = (double)(l1.b - l2.b) / (l2.a - l1.a);
	return X13 < X12;
}

vector<line> L;
void add(long long a, long long b, int id) {
	line d = line(a, b, id);
	if (!L.empty() && L.back().a == d.a) {
		if (L.back().b <= d.b) return; else L.pop_back();
	}
	while(L.size() >= 2 && bad(L[L.size()-2], L[L.size()-1], d)) L.pop_back();
	L.push_back(d);
}

int cur = 0;

pair<long long, int> get(long long x) {
	if (cur >= L.size()) cur = L.size() - 1;
	while(cur < (int)L.size()-1 && L[cur].a * x + L[cur].b > L[cur+1].a * x + L[cur+1].b) ++cur;
	return make_pair(L[cur].a * x + L[cur].b, L[cur].id);
}

const int N = 1e5 + 5, K = 205;
const long long inf = 1e18;

int n, k;
long long a[N];
long long f[N][2];
int trace[N][K];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k; ++k;
	for (int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i-1];

	for (int i = 0; i <= n; ++i) f[i][0] = f[i][1] = inf;
	f[0][0] = 0;

	for (int j = 1; j <= k; ++j) {
		L.clear();
		cur = 0;
		add(0, f[0][0], 0);
		for (int i = 1; i <= n; ++i) {
			pair<long long, int> res = get(a[i]);
			if (f[i][1] > res.first + a[i] * a[i]){
				trace[i][j] = res.second;
				f[i][1] = res.first + a[i] * a[i];
			}
			add(-2 * a[i], f[i][0] + a[i] * a[i], i);
		}
		for (int i = 0; i <= n; ++i) f[i][0] = f[i][1], f[i][1] = inf;
	}

	long long ans = f[n][0];
	ans = (a[n] * a[n] - ans) / 2;

	printf("%lld\n", ans);
	vector<int> vec;
	while(n) {
		n = trace[n][k]; --k;
		vec.push_back(n);
	}
	vec.pop_back();
	for (int i = vec.size()-1; i >= 0; --i) printf("%d ", vec[i]); printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> get(long long int)':
sequence.cpp:28:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (cur >= L.size()) cur = L.size() - 1;
          ^

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