// Andrei-Costin Constantinescu
// O(N) - Dynamic Programming
#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
const int NMAX = 2000000;
int N, K;
int A[2 * NMAX + 5]; // Subjects
int B[2 * NMAX + 5]; // Textbooks
typedef long long int lint;
const lint INF = 2E16L;
lint sPartB[2 * NMAX + 5];
inline lint getSPartB(int l, int r) {
assert(1 <= l && 1 <= r && l <= 2 * N && r <= 2 * N && l <= r);
return sPartB[r] - sPartB[l - 1];
}
lint taken[NMAX], notTaken[NMAX];
inline void updateDp(lint &where, const lint val) {
if (val > where)
where = val;
}
lint computeDp(bool forceFirst) {
for (int i = 0; i <= N; ++ i)
taken[i] = notTaken[i] = -INF;
if (forceFirst)
taken[1] = A[1] - getSPartB(1, K);
else
notTaken[1] = 0;
lint ans = -INF;
for (int i = 1; i <= N; ++ i) {
// notTaken[i] -> taken[i], decrease less if ForceFirst
if (!forceFirst)
updateDp(taken[i], notTaken[i] + A[i] - getSPartB(i, i + K - 1));
else
updateDp(taken[i], notTaken[i] + A[i] - getSPartB(i, min(N, i + K - 1)));
updateDp(ans, taken[i]), updateDp(ans, notTaken[i]);
// taken[i] - B[i + K] + A[i + K] -> taken[i + 1]
if (i + 1 <= N) {
if (!forceFirst || i + K <= N)
updateDp(taken[i + 1], taken[i] - B[i + K] + A[i + 1]);
else
updateDp(taken[i + 1], taken[i] + A[i + 1]);
}
// taken[i] -> notTaken[i + K];
if (i + K <= N)
updateDp(notTaken[i + K], taken[i]);
// notTaken[i] -> notTaken[i + 1]
if (i + 1 <= N)
updateDp(notTaken[i + 1], notTaken[i]);
}
if (ans < 0)
return 0;
else
return ans;
}
lint solve(int n, int k, int a[], int b[]) {
N = n, K = k;
for (int i = 1; i <= N; ++ i) {
A[i] = a[i - 1];
A[N + i] = A[i];
}
for (int i = 1; i <= N; ++ i) {
B[i] = b[i - 1];
B[N + i] = B[i];
}
for (int i = 1; i <= 2 * N; ++ i)
sPartB[i] = sPartB[i - 1] + B[i];
return max(computeDp(false), computeDp(true));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
536 KB |
Output is correct |
3 |
Correct |
3 ms |
564 KB |
Output is correct |
4 |
Correct |
3 ms |
564 KB |
Output is correct |
5 |
Correct |
2 ms |
564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
536 KB |
Output is correct |
3 |
Correct |
3 ms |
564 KB |
Output is correct |
4 |
Correct |
3 ms |
564 KB |
Output is correct |
5 |
Correct |
2 ms |
564 KB |
Output is correct |
6 |
Correct |
3 ms |
828 KB |
Output is correct |
7 |
Correct |
6 ms |
868 KB |
Output is correct |
8 |
Correct |
4 ms |
868 KB |
Output is correct |
9 |
Correct |
3 ms |
876 KB |
Output is correct |
10 |
Correct |
4 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
28012 KB |
Output is correct |
2 |
Correct |
7 ms |
28012 KB |
Output is correct |
3 |
Correct |
452 ms |
110224 KB |
Output is correct |
4 |
Correct |
5 ms |
110224 KB |
Output is correct |
5 |
Correct |
15 ms |
110224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
536 KB |
Output is correct |
3 |
Correct |
3 ms |
564 KB |
Output is correct |
4 |
Correct |
3 ms |
564 KB |
Output is correct |
5 |
Correct |
2 ms |
564 KB |
Output is correct |
6 |
Correct |
3 ms |
828 KB |
Output is correct |
7 |
Correct |
6 ms |
868 KB |
Output is correct |
8 |
Correct |
4 ms |
868 KB |
Output is correct |
9 |
Correct |
3 ms |
876 KB |
Output is correct |
10 |
Correct |
4 ms |
876 KB |
Output is correct |
11 |
Correct |
79 ms |
28012 KB |
Output is correct |
12 |
Correct |
7 ms |
28012 KB |
Output is correct |
13 |
Correct |
452 ms |
110224 KB |
Output is correct |
14 |
Correct |
5 ms |
110224 KB |
Output is correct |
15 |
Correct |
15 ms |
110224 KB |
Output is correct |
16 |
Incorrect |
315 ms |
110224 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |