#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
const int M = 19;
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 ans = 0;
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";
}
Compilation message
homecoming.cpp: In function 'll solve(int, int, int*, int*)':
homecoming.cpp:52:8: warning: unused variable 'ans' [-Wunused-variable]
52 | ll ans = 0;
| ^~~
homecoming.cpp: In function 'll solve2(int, int, int*, int*)':
homecoming.cpp:94:8: warning: unused variable 'ans' [-Wunused-variable]
94 | ll ans = 0;
| ^~~
/usr/bin/ld: /tmp/ccX01FeS.o: in function `main':
homecoming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEWPINS.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
