Submission #21821

#	Time	Username	Problem	Language	Result	Execution time	Memory
21821		dcordb	Split the sequence (APIO14_sequence)	C++11	33 / 100	9 ms	5268 KiB

sequence

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

typedef long long int64;
const int MAX = 1e3 + 5;

namespace CH {
	struct rect {
		int64 n, m;
		int id;

		rect() {}

		rect(int64 n, int64 m, int id) : n(n), m(m), id(id) {}

		int64 eval(int64 x) {
			return m * x + n;
		}
	};

	int k, opt;
	rect stk[MAX];

	void init() {
		k = 0, opt = 1;
	}

	bool bad_line(rect l1, rect l2, rect l3) {
		return (l1.n - l3.n) * (l2.m - l1.m) < (l3.m - l1.m) * (l1.n - l2.n);
	}

	void add(rect r) {
		while(k > 1 && bad_line(stk[k - 1], stk[k], r))
			k--;
		stk[++k] = r;
	}

	pair <int64, int> query(int64 x) {
		if(k == 0)
			return { -1, -1 };

		if(opt > k)
			opt = k;

		while(opt < k && stk[opt].eval(x) <= stk[opt + 1].eval(x))
			opt++;

		return { stk[opt].eval(x), stk[opt].id };
	}
}

int n, k;
pair <int, int> p[MAX][205];
int64 t[MAX], dp[MAX][205];
vector <int64> ans;

int main() {
	scanf("%d%d", &n, &k);

	k++;

	for(int i = 1; i <= n; i++) {
		int x; scanf("%d", &x);
		t[i] = t[i - 1] + x;
	}

	memset(dp, -1, sizeof(dp));

	dp[0][0] = 0;

	for(int l = 1; l <= k; l++) {
		CH::init();
		for(int i = 1; i <= n; i++) {
			if(dp[i - 1][l - 1] != -1)
				CH::add(CH::rect(dp[i - 1][l - 1] - t[i - 1] * t[i - 1], t[i - 1], i - 1));

			auto o = CH::query(2LL * t[i] - t[n]);
			dp[i][l] = o.first;

			if(dp[i][l] != -1) {
				dp[i][l] += t[i] * t[n] - t[i] * t[i];
				p[i][l] = { o.second, l - 1 };
			}
		}
	}

	printf("%lld\n", dp[n][k] / 2);

	int x = n, y = k;

	while(1) {
		if(x == 0)
			break;

		ans.push_back(x);

		int nx = p[x][y].first;
		int ny = p[x][y].second;

		x = nx, y = ny;
	}

	reverse(ans.begin(), ans.end());
	ans.pop_back();

	for(int i = 0; i < (int) ans.size(); i++) {
		printf("%lld", ans[i]);
		printf(i == (int) ans.size() - 1 ? "\n" : " ");
	}

	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:58:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:63:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^

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