#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5;
int K;
template<typename T>
struct Deq {
vector<T> v;
void push_front(T x) { v.emplace_back(x); }
T& operator[](const int& x) { return rbegin(v)[x]; }
void resize(int k) {
if(k >= sz(v)) return;
v.erase(begin(v), begin(v) + sz(v) - k);
return;
}
int size() { return sz(v); }
}; // trebuie facut persistent
struct Tree {
vector<int> g[nmax];
int p[nmax];
void add_edge(int a, int b) {
g[a].emplace_back(b);
p[b] = a;
}
struct mdeq : Deq<ll> {
ll lazy = 0;
};
mdeq dp[nmax];
int calculated[nmax];
Tree() {
memset(calculated, 0, sizeof(calculated));
}
template<class CB, class CB2> void calcdp(CB&& cost, CB2 atr, int node) {
if(calculated[node]) return;
calculated[node] = 1;
for(auto x : g[node]) {
cerr << node << " <-- " << x << '\n';
calcdp(cost, atr, x);
dp[x].resize(K);
bool swapped = 0;
auto T = dp[x];
if(sz(T) > sz(dp[node]))
swap(T, dp[node]);
for(int i = 0; i < sz(T); i++)
dp[node][i] = max(T[i] + T.lazy - dp[node].lazy, dp[node][i]);
}
dp[node].push_front(cost(node) - dp[node].lazy);
dp[node].lazy += atr(node);
//cerr << node << ' ' << cost(node) << ' ' << atr(node) << ": ";
//for(int i = 0; i < sz(dp[node]); i++) cerr << dp[node][i] + dp[node].lazy << ' ';
//cerr << '\n';
return;
}
};
ll spart[nmax];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n >> K;
for(int i = 1, x; i <= n; i++) {
cin >> spart[i];
spart[i] += spart[i - 1];
}
vector<int> v(n + 1);
for(auto &x : v | views::drop(1)) cin >> x;
Tree toleft, toright;
vector<int> st;
for(int i = 1; i <= n; i++) {
while(sz(st) && v[st.back()] <= v[i]) st.pop_back();
if(sz(st) == 0) toleft.add_edge(0, i);
else toleft.add_edge(st.back(), i), toright.add_edge(i, st.back());
st.emplace_back(i);
}
st.clear();
for(int i = n; i > 0; i--) {
while(sz(st) && v[st.back()] < v[i]) st.pop_back();
if(sz(st) == 0) toright.add_edge(0, i);
else toright.add_edge(st.back(), i), toleft.add_edge(i, st.back());
st.emplace_back(i);
}
st.clear();
toleft.calcdp([&](int x) { return x == 0? 0 : -spart[x]; }, [&](int x) { return v[x]; }, 0);
toright.calcdp([&](int x) { return x == 0? 0 : spart[x - 1]; }, [&](int x) { return v[x]; }, 0);
ll best_cost = -1e18;
for(int P = 1; P <= n; P++) {
auto& X = toleft.dp[P];
auto& Y = toright.dp[P];
//cerr << sz(X) << ' ' << sz(Y) << '\n';
if(sz(X) > sz(Y)) swap(X, Y);
for(int i = 0; i < min(K, sz(X)); i++) {
int j = K - i - 1;
if(j >= sz(Y)) continue;
best_cost = max(best_cost, X[i] + Y[j] + X.lazy + Y.lazy - v[P]);
}
}
cout << best_cost << '\n';
}
/**
Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/
Compilation message
trade.cpp: In function 'int main()':
trade.cpp:83:19: warning: unused variable 'x' [-Wunused-variable]
83 | for(int i = 1, x; i <= n; i++) {
| ^
trade.cpp:89:22: error: 'views' has not been declared
89 | for(auto &x : v | views::drop(1)) cin >> x;
| ^~~~~
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]':
trade.cpp:110:94: required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
57 | bool swapped = 0;
| ^~~~~~~
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]':
trade.cpp:111:98: required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>&; CB2 = main()::<lambda(int)>]':
trade.cpp:55:16: required from 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]'
trade.cpp:110:94: required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>&; CB2 = main()::<lambda(int)>]':
trade.cpp:55:16: required from 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]'
trade.cpp:111:98: required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
