#ifndef EVAL
#include "homecoming.h"
#endif
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 2e6 + 5;
ll dp[N][2], pa[N], pb[N];
ll solve(int n, int k, int a[], int b[]){
for(int i=0;i<n;i++){
pa[i] = a[i];
if(i) pa[i] += pa[i-1];
pb[i] = b[i];
if(i) pb[i] += pb[i-1];
}
memset(dp, 254, sizeof dp);
dp[0][1] = a[0] - pb[k - 1];
for(int i=1;i<n;i++){
dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
dp[i][1] = max(dp[i-1][1] + a[i] - (i + k - 1 < n ? b[i + k - 1] : 0),
dp[i-1][0] + a[i] - (pb[min(i + k - 1, n - 1)] - pb[i - 1]));
}
ll res = max(dp[n - 1][0], dp[n - 1][1]);
memset(dp, 254, sizeof dp);
dp[0][0] = 0;
for(int i=1;i<n;i++){
dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
dp[i][1] = max(dp[i-1][1] + a[i] - b[(i + k - 1) % n],
dp[i-1][0] + a[i] - (pb[min(i + k - 1, n - 1)] - pb[i - 1] + (i + k > n ? pb[i + k - 1 - n] : 0)));
}
res = max({res, dp[n - 1][0], dp[n - 1][1]});
return res;
}
/*
1
3 2
40 80 100
140 0 20
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
31572 KB |
Output is correct |
2 |
Correct |
21 ms |
31588 KB |
Output is correct |
3 |
Correct |
133 ms |
31648 KB |
Output is correct |
4 |
Correct |
19 ms |
31576 KB |
Output is correct |
5 |
Correct |
39 ms |
31620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
31572 KB |
Output is correct |
2 |
Correct |
21 ms |
31588 KB |
Output is correct |
3 |
Correct |
133 ms |
31648 KB |
Output is correct |
4 |
Correct |
19 ms |
31576 KB |
Output is correct |
5 |
Correct |
39 ms |
31620 KB |
Output is correct |
6 |
Correct |
18 ms |
31732 KB |
Output is correct |
7 |
Correct |
17 ms |
31768 KB |
Output is correct |
8 |
Correct |
40 ms |
31676 KB |
Output is correct |
9 |
Correct |
18 ms |
31740 KB |
Output is correct |
10 |
Execution timed out |
1086 ms |
31572 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
43340 KB |
Output is correct |
2 |
Correct |
218 ms |
31788 KB |
Output is correct |
3 |
Correct |
147 ms |
78604 KB |
Output is correct |
4 |
Correct |
22 ms |
32212 KB |
Output is correct |
5 |
Correct |
714 ms |
32284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
31572 KB |
Output is correct |
2 |
Correct |
21 ms |
31588 KB |
Output is correct |
3 |
Correct |
133 ms |
31648 KB |
Output is correct |
4 |
Correct |
19 ms |
31576 KB |
Output is correct |
5 |
Correct |
39 ms |
31620 KB |
Output is correct |
6 |
Correct |
18 ms |
31732 KB |
Output is correct |
7 |
Correct |
17 ms |
31768 KB |
Output is correct |
8 |
Correct |
40 ms |
31676 KB |
Output is correct |
9 |
Correct |
18 ms |
31740 KB |
Output is correct |
10 |
Execution timed out |
1086 ms |
31572 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |