#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;
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 = 0; i < K; i++) {
Do();
Rotate();
}
for (i = 1; i <= n; i++)res -= B[i];
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
376 KB |
Output is correct |
3 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
376 KB |
Output is correct |
3 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
16152 KB |
Output is correct |
2 |
Incorrect |
29 ms |
16152 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
376 KB |
Output is correct |
3 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |