#include "homecoming.h"
#include <algorithm>
#define N_ 2010000
using namespace std;
int A[N_], B[N_], n, K;
long long D[N_][2], res;
void Do() {
int i;
for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
D[1][0] = B[1];
for (i = 2; i <= n; i++) {
D[i][0] = D[i - 1][0] + B[i];
if (i >= K)D[i][0] = max(D[i][0], D[i - K + 1][1]);
D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
}
res = max(res, D[n][0]);
for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
D[1][1] = A[1];
for (i = 2; i <= n; i++) {
D[i][0] = D[i - 1][0] + B[i];
if (i >= K)D[i][0] = max(D[i][0], D[i - K + 1][1]);
D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
}
res = max(res, max(D[n][0], D[n][1]));
}
void Rotate() {
int i;
int ta = A[1], tb = B[1];
for (i = 1; i < n; i++)A[i] = A[i + 1], B[i] = B[i + 1];
A[n] = ta, B[n] = tb;
}
long long int solve(int N, int k, int *a, int *b) {
int i;
res = 0;
n = N, K = k;
if (K == 1) {
long long r = 0;
for (i = 0; i < n; i++) {
r += max(a[i]-b[i],0);
}
return r;
}
for (i = 1; i <= n; i++)A[i] = a[i - 1], B[i] = b[i - 1];
for (i = 1; i <= n; i++)res += A[i];
for (i = 0; i <= K; i++) {
Do();
Rotate();
}
for (i = 1; i <= n; i++)res -= B[i];
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
4 ms |
480 KB |
Output is correct |
5 |
Correct |
4 ms |
480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
4 ms |
480 KB |
Output is correct |
5 |
Correct |
4 ms |
480 KB |
Output is correct |
6 |
Correct |
332 ms |
712 KB |
Output is correct |
7 |
Correct |
255 ms |
712 KB |
Output is correct |
8 |
Correct |
47 ms |
712 KB |
Output is correct |
9 |
Correct |
9 ms |
720 KB |
Output is correct |
10 |
Correct |
4 ms |
720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
107 ms |
16208 KB |
Output is correct |
2 |
Correct |
29 ms |
16208 KB |
Output is correct |
3 |
Correct |
146 ms |
16312 KB |
Output is correct |
4 |
Correct |
32 ms |
16312 KB |
Output is correct |
5 |
Correct |
38 ms |
16312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
4 ms |
480 KB |
Output is correct |
5 |
Correct |
4 ms |
480 KB |
Output is correct |
6 |
Correct |
332 ms |
712 KB |
Output is correct |
7 |
Correct |
255 ms |
712 KB |
Output is correct |
8 |
Correct |
47 ms |
712 KB |
Output is correct |
9 |
Correct |
9 ms |
720 KB |
Output is correct |
10 |
Correct |
4 ms |
720 KB |
Output is correct |
11 |
Correct |
107 ms |
16208 KB |
Output is correct |
12 |
Correct |
29 ms |
16208 KB |
Output is correct |
13 |
Correct |
146 ms |
16312 KB |
Output is correct |
14 |
Correct |
32 ms |
16312 KB |
Output is correct |
15 |
Correct |
38 ms |
16312 KB |
Output is correct |
16 |
Execution timed out |
1073 ms |
63244 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |