Submission #34829

#	Time	Username	Problem	Language	Result	Execution time	Memory
34829		cheater2k	Split the sequence (APIO14_sequence)	C++14	71 / 100	2000 ms	90276 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) {}
};

vector<line> L;
vector<double> X;

double intersect(line p, line q) {
	return (double)(p.b - q.b) / (q.a - p.a);
}

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();
			if (X.size()) X.pop_back();
		}
	}
	while(L.size() >= 2) {
		double curX = intersect(d, L[L.size()-2]);
		if (curX < X.back()) X.pop_back(), L.pop_back(); else break;
	}
	if (L.size() > 0) {
		double curX = intersect(d, L.back());
		X.push_back(curX);
	}
	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] = inf;
	f[0][0] = 0;

	for (int j = 1; j <= k; ++j) {
		L.clear();
		X.clear();
		cur = 0;
		add(0, f[0][0], 0);
		for (int i = 1; i <= n; ++i) {
			f[i][1] = inf;
			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);
			f[i][0] = f[i][1];
		}
		f[0][0] = 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:39: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