#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll solve(int n, int k, int *a, int *b) {
vector<ll> a_pre(1);
for (int i = 0; i < n; i++)
a_pre.push_back(a_pre.back() + a[i]);
for (int i = 0; i < n; i++)
a_pre.push_back(a_pre.back() + a[i]);
vector<ll> first_cost(n);
for (int i = 0; i < k; i++)
first_cost[0] += b[i];
for (int i = 1; i < n; i++) {
first_cost[i] = first_cost[i - 1] + b[(i + k - 1) % n] - b[i - 1];
}
vector<ll> self_profit(n);
vector<ll> self_profit_pre(1);
for (int i = 0; i < n; i++) {
self_profit[i] = a[i] - b[(i + k - 1) % n];
self_profit_pre.push_back(self_profit_pre.back() + self_profit[i]);
}
for (int i = 0; i < n; i++) {
self_profit_pre.push_back(self_profit_pre.back() + self_profit[i]);
}
vector<ll> max_total_self_profit(2 * n, -1);
deque<array<ll, 2>> q;
for (int i = 2 * n - 1; i >= 0; i--) {
while (q.size() && q.front()[0] - i > n - k)
q.pop_front();
ll pre = self_profit_pre[i + 1];
while (q.size() && q.back()[1] < pre)
q.pop_back();
if (q.size())
max_total_self_profit[i] = q.front()[0];
else
max_total_self_profit[i] = i;
// max_total_self_cost[i] = max(max_total_self_cost[i], self_profit_pre[max(0, i + 1 - (n - k))]);
q.push_back({i, pre});
}
// cout << "max_total_self_profit ";
// for (int i = 0; i < n; i++) {
// cout << max_total_self_profit[i] << " ";
// }
// cout << "\n";
ll dp[n + 1] = {};
for (int i = 0; i < n; i++) {
dp[i + 1] = max(dp[i + 1], dp[i]);
ll cur = a[i] - first_cost[i];
// self cost: i+1 ... i+n-k
// a only: i+n-k+1 ... i+n-1
ll a1 = cur;
ll a2 = cur + self_profit_pre[max_total_self_profit[i] + 1] - self_profit_pre[i + 1];
ll a3 = cur + self_profit_pre[i + n - k + 1] - self_profit_pre[i + 1] + a_pre[i + n] - a_pre[i + n - k + 1];
int nxt = i;
ll best = 0;
if (a1 > a2 && a1 > a3 && a1 >= 0) {
nxt = (i + k - 1) % n;
best = a1;
} else if (a2 >= a1 && a2 > a3 && a2 >= 0) {
nxt = (max_total_self_profit[i] + k - 1) % n;
best = a2;
} else if (a3 >= a2 && a3 >= a1 && a3 >= 0) {
nxt = (i + n - 1) % n;
best = a3;
}
// cout << i << " " << a1 << " " << a2 << " " << a3 << " " << nxt << " " << best << "\n";
dp[nxt + 1] = max(dp[nxt + 1], dp[i] + best);
// cout << i << " " << cur << " " << max_total_self_profit[i] << " "
// << self_profit_pre[max_total_self_profit[i] + 1] - self_profit_pre[i + 1] << "\n";
// ans =
// max({ans, cur, cur + self_profit_pre[max_total_self_profit[i] + 1] - self_profit_pre[i + 1],
// cur + self_profit_pre[i + n - k + 1] - self_profit_pre[i + 1] + a_pre[i + n] - a_pre[i + n - k +
// 1]});
}
// for (ll x : dp)
// cout << x << " ";
// cout << "\n";
return *max_element(dp, dp + n + 1);
}
// ll solve2(int n, int k, int *a, int *b) {
// ll ans = 0;
// ll dp[n + 1] = {};
// for (int i = 0; i < n; i++) {
// // for(int j = i; j < n; j++){
// // ll cur = 0;
// // for(int jj = i; jj <= j)
// // bool vis[n] = {};
// // for(int offset = 0; offset < k + j-i; offset++){
// // int idx = (j + offset) % n;
// // if(vis[idx]) continue;
// // vis[idx] = 1;
// // cur -= b[idx];
// // }
// // dp[]
// // }
// }
// // cout << "solve2 dp ";
// // for (int x : dp)
// // cout << x << " ";
// // cout << "\n";
// return *max_element(dp, dp + n + 1);
// }
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// srand(time(0));
// int n = 10; // + rand() % 5;
// int k = 2; // rand() % n + 1;
// cin >> n >> k;
// vector<int> a(n), b(n);
// for (int i = 0; i < n; i++) {
// // a[i] = rand() % 2;
// a[i] = i % 3 == 0;
// // cout << a[i] << " ";
// cin >> a[i];
// }
// for (int i = 0; i < n; i++) {
// // b[i] = rand() % 2;
// b[i] = i % 3 > 0;
// // b[1] = b[4] = 0;
// // cout << b[i] << " ";
// cin >> b[i];
// }
// // int a[] = {40, 80, 100};
// // int b[] = {140, 0, 20};
// ll a1 = solve(n, k, a.data(), b.data());
// cout << a1 << "\n";
// // cout << "ans1 " << a1 << "\n";
// // ll a2 = solve2(n, k, a.data(), b.data());
// // cout << "ans2 " << a2 << "\n";
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
50356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
