#include"homecoming.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2000005;
ll n, k, s[2*N], dt[N], dt2[N];
ll solve (int _N, int _K, int *A, int *B) {
n = _N;
k = _K;
ll R = 0;
for(ll i=0;i<n;i++) {
R += A[i] - B[i];
}
for(int i=0;i<2*n;i++) {
s[i+1] = s[i] + B[i%n];
}
R = max(R, 0ll);
ll M = 0;
dt[0] = A[0] - s[k];
R = max(R, dt[0]);
M = max(M, dt[0]);
for(ll i=1;i<n;i++) {
dt[i] = max(M + A[i] - s[k+i] + s[i], dt[i-1] + A[i] - B[(i+k-1)%n]);
R = max(R, dt[i]);
M = max(M, dt[i]);
}
for(ll C=0,i=1;i<=n-k;i++) {
C += A[n-i] - B[n-i];
dt2[i] = max(dt2[i-1], C);
}
R = max(R, dt[0] + dt2[n-k]);
M = dt[0];
for(ll i=1;i<=n-k;i++) {
dt[i] = max(M + A[i] - s[k+i] + s[i], dt[i-1] + A[i] - B[(i+k-1)%n]);
R = max(R, dt[i] + dt2[n-k-i]);
M = max(M, dt[i]);
}
return R;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
484 KB |
Output is correct |
| 5 |
Correct |
3 ms |
484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
484 KB |
Output is correct |
| 5 |
Correct |
3 ms |
484 KB |
Output is correct |
| 6 |
Correct |
3 ms |
724 KB |
Output is correct |
| 7 |
Correct |
4 ms |
724 KB |
Output is correct |
| 8 |
Correct |
3 ms |
724 KB |
Output is correct |
| 9 |
Correct |
4 ms |
724 KB |
Output is correct |
| 10 |
Correct |
3 ms |
724 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
87 ms |
20112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
20112 KB |
Output is correct |
| 3 |
Correct |
357 ms |
78920 KB |
Output is correct |
| 4 |
Correct |
6 ms |
78920 KB |
Output is correct |
| 5 |
Correct |
20 ms |
78920 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
484 KB |
Output is correct |
| 5 |
Correct |
3 ms |
484 KB |
Output is correct |
| 6 |
Correct |
3 ms |
724 KB |
Output is correct |
| 7 |
Correct |
4 ms |
724 KB |
Output is correct |
| 8 |
Correct |
3 ms |
724 KB |
Output is correct |
| 9 |
Correct |
4 ms |
724 KB |
Output is correct |
| 10 |
Correct |
3 ms |
724 KB |
Output is correct |
| 11 |
Correct |
87 ms |
20112 KB |
Output is correct |
| 12 |
Correct |
7 ms |
20112 KB |
Output is correct |
| 13 |
Correct |
357 ms |
78920 KB |
Output is correct |
| 14 |
Correct |
6 ms |
78920 KB |
Output is correct |
| 15 |
Correct |
20 ms |
78920 KB |
Output is correct |
| 16 |
Correct |
335 ms |
78920 KB |
Output is correct |
| 17 |
Correct |
157 ms |
78920 KB |
Output is correct |
| 18 |
Correct |
254 ms |
78920 KB |
Output is correct |
| 19 |
Correct |
282 ms |
78920 KB |
Output is correct |
| 20 |
Correct |
272 ms |
78920 KB |
Output is correct |
| 21 |
Correct |
325 ms |
78920 KB |
Output is correct |
