| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 682148 | chessmayimayi | Homecoming (BOI18_homecoming) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
ll solve(int n, int k, int aa[], int bb[]) {
vector<ll> b(n + 1), a(n + 1), suma(n + 1), sumb(n + 1);
rep1(i, n) {
a[i] = aa[i - 1];
suma[i] += suma[i - 1] + a[i];
}
rep1(i, n) {
b[i] = bb[i - 1];
sumb[i] += sumb[i - 1] + b[i];
}
dd(a);
dd(b);
vll dp(n + 1);
vll take(n + 1);
// A1 is taken;
take[1] = a[1] - sumb[k];
dp[1] = take[1];
rep2(i, 2, n) {
if (i + k - 1 <= n) {
take[i] = max(take[i - 1] + a[i] - b[i + k - 1],
dp[i - 1] + a[i] - sumb[i + k - 1] + sumb[i - 1]);
} else {
take[i] = max(take[i - 1] + a[i], dp[i - 1] + sumb[n] - sumb[i - 1]);
}
dp[i] = max(dp[i - 1], take[i]);
}
ll res = 0;
res = max(res, dp[n]);
dp.clear();
dp.resize(n + 1);
take.clear();
take.resize(n + 1);
// A1 is not taken;
take[1] = -inf;
dp[1] = -inf;
rep2(i, 2, n) {
if (i + k - 1 <= n) {
take[i] = max(take[i - 1] + a[i] - b[i + k - 1],
dp[i - 1] + a[i] - sumb[i + k - 1] + sumb[i - 1]);
} else {
take[i] = max(take[i - 1] + a[i] - b[i + k - 1],
dp[i - 1] + sumb[n] - sumb[i - 1] + sumb[i + k - 1 - n]);
}
dp[i] = max(dp[i - 1], take[i]);
}
res = max(res, dp[n]);
return res;
}