#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=250005, inf=1e18;
ll n, k, c[nx], s[nx], qs[nx], dp[nx], ans=-inf;
vector<pair<ll, ll>> srt;
struct wavelettree
{
struct node
{
vector<ll> f={0}, qs={0};
} d[4*nx];
void update(int l, int r, int i, int tidx, int idx)
{
if (l==r) return d[i].qs.push_back(s[idx]), void();
int md=(l+r)/2;
d[i].qs.push_back(d[i].qs.back()+(tidx>md?s[idx]:0));
d[i].f.push_back(d[i].f.back()+(tidx>md?1:0));
if (tidx<=md) update(l, md, 2*i, tidx, idx);
else update(md+1, r, 2*i+1, tidx, idx);
}
ll query(int l, int r, int i, int idxl, int idxr, int key)
{
/*
cout<<"query "<<l<<' '<<r<<' '<<idxl<<' '<<idxr<<' '<<d[i].qs.size()<<'\n';
cout<<"key "<<key<<'\n';
if (i==1)
{
cout<<"f : ";
for (auto x:d[i].f) cout<<x<<' ';
cout<<'\n';
}*/
if (l==r) return d[i].qs.back();
int md=(l+r)/2;
if (d[i].f[idxr]-d[i].f[idxl-1]>=key) return query(md+1, r, 2*i+1, d[i].f[idxl-1]+1, d[i].f[idxr-1]+1, key);
else return d[i].qs[idxr]-d[i].qs[idxl-1]+query(l, md, 2*i, idxl-1-d[i].f[idxl-1]+1, idxr-1-d[i].f[idxr-1]+1, key-(d[i].f[idxr]-d[i].f[idxl-1]));
}
} w;
void solve(int l, int r, int optl, int optr)
{
if (r<l) return;
int md=(l+r)/2;
pair<ll, ll> mx={-inf, 0};
for (int i=optl; i<=min((ll)optr, md-k+1); i++) mx=max(mx, {-qs[md]+qs[i-1]+w.query(1, n, 1, i, md, k), i});
dp[md]=mx.first;
solve(l, md-1, optl, mx.second);
solve(md+1, r, mx.second, optr);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>c[i], qs[i]=qs[i-1]+c[i], dp[i]=-inf;
for (int i=1; i<=n; i++) cin>>s[i], srt.push_back({s[i], i});
sort(srt.begin(), srt.end());
for (int i=1; i<=n; i++)
{
auto tmp=lower_bound(srt.begin(), srt.end(), make_pair(s[i], (ll)i))-srt.begin()+1;
w.update(1, n, 1, tmp, i);
}
//for (int i=1; i<=n; i++) cout<<"debug wavelet "<<w.query(1, n, 1, 1, n, i)<<'\n';
//return 0;
solve(k, n, 1, n);
for (int i=1; i<=n; i++) ans=max(ans, dp[i]);
cout<<ans<<'\n';
for (int i=1; i<=n; i++) cout<<0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |