oj.uz

Submission #20893

# Submission time Handle Problem Language Result Execution time Memory
20893 2017-03-08T13:35:18 Z Supernova Split the sequence (APIO14_sequence) C++11
0 / 100
 0 ms 87848 KB 
#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;
	
	freopen("13.in", "r", stdin);
	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

sequence.cpp: In function 'int main()':
sequence.cpp:28:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("13.in", "r", stdin);
                              ^
sequence.cpp:29: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:31: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 87848 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 87848 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 87848 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 87848 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 87848 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 87848 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -