제출 #20890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20890		Supernova	수열 (APIO14_sequence)	C++11	0 / 100	1193 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) {
	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; i--) printf("%d ", k), k = path[i - 1][k];
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:27: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:29: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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29