Submission #376573

#	Time	Username	Problem	Language	Result	Execution time	Memory
376573		rainboy	Split the sequence (APIO14_sequence)	C11	100 / 100	145 ms	5612 KiB

sequence

#include <stdio.h>

#define N	100000

double cross2(double x1, double y1, double x2, double y2) {
	return x1 * y2 - x2 * y1;
}

long long xx[N + 1], yy[N + 1];

double cross(int i, int j, int k) {
	return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}

long long eval(int i, int x) {
	return xx[i] * x + yy[i];
}

void solve(int *aa, long long *dp, int *kk, int n, long long c) {
	static int qu[N + 1];
	int i, head, cnt;

	dp[0] = 0, xx[0] = aa[0], yy[0] = dp[0] - aa[0] * aa[0];
	head = cnt = 0, qu[head + cnt++] = 0;
	for (i = 1; i <= n; i++) {
		while (cnt >= 2 && eval(qu[head], aa[i]) < eval(qu[head + 1], aa[i]))
			head++, cnt--;
		dp[i] = eval(qu[head], aa[i]) - c, kk[i] = kk[qu[head]] + 1;
		xx[i] = aa[i], yy[i] = dp[i] - (long long) aa[i] * aa[i];
		while (cnt >= 2 && cross(qu[head + cnt - 2], qu[head + cnt - 1], i) >= 0)
			cnt--;
		qu[head + cnt++] = i;
	}
}

int main() {
	static long long dp[N + 1], dq[N + 1];
	static int aa[N + 1], kk[N + 1], ll[N + 1];
	static char used[N];
	int n, k, i, j;
	long long lower, upper, x;

	scanf("%d%d", &n, &k), k++;
	for (i = 1; i <= n; i++) {
		scanf("%d", &aa[i]);
		aa[i] += aa[i - 1];
	}
	lower = -1, upper = 1000000000000000000;
	while (upper - lower > 1) {
		long long c = (lower + upper) / 2;

		solve(aa, dp, kk, n, c);
		if (kk[n] <= k)
			upper = c;
		else
			lower = c;
	}
	solve(aa, dp, kk, n, upper);
	solve(aa, dq, ll, n, upper - 1);
	printf("%lld\n", dp[n] + upper * k);
	for (i = n - 1, j = n, x = dp[j]; i >= 0; i--)
		if (kk[i] <= k - 1 && k - 1 <= ll[i] && dp[i] + (long long) (aa[j] - aa[i]) * aa[i] - upper == x)
			used[i] = 1, j = i, x = dp[j], k--;
	for (i = 1; i < n; i++)
		if (used[i])
			printf("%d ", i);
	printf("\n");
	return 0;
}

Compilation message (stderr)

sequence.c: In function 'main':
sequence.c:43:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d%d", &n, &k), k++;
      |  ^~~~~~~~~~~~~~~~~~~~~
sequence.c:45:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

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