#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL reallybad = -10000000000000000LL;
LL test(int n, int k, vector<LL> a, vector<LL> b, int x){
LL ans = reallybad;
vector<LL> newa;
vector<LL> newb;
vector<LL> bpsums(1,0);
for(int i = 0; i < n; i++){
newa.push_back(a[(i+x) % n]);
newb.push_back(b[(i+x) % n]);
}
for(int i = 0; i < n; i++){
bpsums.push_back(bpsums[i] + newb[i]);
}
for(int y = 0; y < 2; y++){
vector<LL> dp0(n+1, reallybad);
vector<LL> dp1(n+1, reallybad);
if(y == 0) dp0[0] = 0;
if(y == 1) dp1[0] = 0;
for(int i = 0; i <= n; i++){
dp1[i] = max(dp1[i], dp0[i]);
if(i + 1 <= n){
dp0[i+1] = max(dp0[i+1], dp0[i]);
dp1[i+1] = max(dp1[i+1], dp1[i] + newa[i] - newb[i]);
}
if(i + k <= n){
dp0[i+k] = max(dp0[i+k], dp1[i] - bpsums[i+k] + bpsums[i]);
}
}
if(y == 0) ans = max(ans, dp0[n]);
if(y == 1) ans = max(ans, dp1[n]);
}
return ans;
}
long long solve(int N, int K, int *A, int *B){
int n = N;
int k = K;
k--;
vector<LL> a, b;
for(int i = 0; i < n; i++){
a.push_back(A[i]);
b.push_back(B[i]);
}
LL ans = 0;
if(k == 0){
for(int i = 0; i < n; i++){
if(a[i] >= b[i]){
ans += a[i] - b[i];
}
}
return ans;
}
LL best = 0;
LL bestidx = 0;
LL sum = 0;
for(int i = 0; i < k; i++){
sum += a[i] - b[i];
if(sum > best){
best = sum;
bestidx = i;
}
}
ans = max(ans, test(n, k, a, b, 0));
//ans = max(ans, test(n, k, a, b, k-1));
ans = max(ans, test(n, k, a, b, bestidx));
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
576 KB |
Output is correct |
3 |
Correct |
3 ms |
576 KB |
Output is correct |
4 |
Correct |
5 ms |
576 KB |
Output is correct |
5 |
Correct |
3 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
576 KB |
Output is correct |
3 |
Correct |
3 ms |
576 KB |
Output is correct |
4 |
Correct |
5 ms |
576 KB |
Output is correct |
5 |
Correct |
3 ms |
576 KB |
Output is correct |
6 |
Correct |
3 ms |
964 KB |
Output is correct |
7 |
Correct |
4 ms |
964 KB |
Output is correct |
8 |
Correct |
4 ms |
964 KB |
Output is correct |
9 |
Correct |
6 ms |
964 KB |
Output is correct |
10 |
Incorrect |
6 ms |
964 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
41168 KB |
Output is correct |
2 |
Correct |
8 ms |
41168 KB |
Output is correct |
3 |
Correct |
198 ms |
47904 KB |
Output is correct |
4 |
Correct |
8 ms |
47904 KB |
Output is correct |
5 |
Incorrect |
21 ms |
47904 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
576 KB |
Output is correct |
3 |
Correct |
3 ms |
576 KB |
Output is correct |
4 |
Correct |
5 ms |
576 KB |
Output is correct |
5 |
Correct |
3 ms |
576 KB |
Output is correct |
6 |
Correct |
3 ms |
964 KB |
Output is correct |
7 |
Correct |
4 ms |
964 KB |
Output is correct |
8 |
Correct |
4 ms |
964 KB |
Output is correct |
9 |
Correct |
6 ms |
964 KB |
Output is correct |
10 |
Incorrect |
6 ms |
964 KB |
Output isn't correct |