Submission #23216

#	Time	Username	Problem	Language	Result	Execution time	Memory
23216		14kg	Split the sequence (APIO14_sequence)	C++11	100 / 100	1203 ms	87844 KiB

sequence

#include <stdio.h>
#define N 100010
#define INF 999999999999999999
 
struct Line {
	long long m, b;
	int path;
} stack[N];
int n, m, sw, stack_len, path[210][N];
long long d[2][N], s[N];
 
long double cross(Line x, Line y) {
	if (x.m == y.m) return -INF;
	return (y.b - x.b) / (x.m - y.m);
}
void push(Line line) {
	if (line.m == 0) stack_len = 0, sw = 1;
	while (stack_len > sw && cross(stack[stack_len - 1], stack[stack_len]) > cross(stack[stack_len], line)) stack_len--;
	stack[++stack_len] = line;
}
long long get(long long x) {
	while (sw < stack_len && stack[sw].m*x + stack[sw].b <= stack[sw + 1].m*x + stack[sw + 1].b) sw++;
	return stack[sw].m*x + stack[sw].b;
}
int main() {
	int x;
	
	scanf("%d %d", &n, &m), m++;
	for (int i = 1; i <= n; i++)
		scanf("%d", &x), s[i] = s[i - 1] + (long long)x;
 
	for (int i = 1; i <= n; i++) d[1][i] = 0;
	for (int i = 2; i <= m; i++) {
		stack[sw = stack_len = 1] = { 0,-INF };
		for (int j = i - 1; j <= n; j++) {
			d[i % 2][j] = get(s[j]), path[i][j] = stack[sw].path;
			push({ s[j], d[(i + 1) % 2][j] - s[j] * s[j], j });
		}
	} printf("%lld\n", d[m % 2][n]);
	for (int i = m, k = path[m][n]; i >= 2; k = path[--i][k]) printf("%d ", k);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:28:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m), m++;
                             ^
sequence.cpp:30:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x), s[i] = s[i - 1] + (long long)x;
                                                  ^

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