#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 persist
{
struct node
{
ll f, sm;
node *l, *r;
node(): f(0), sm(0), l(0), r(0){}
};
typedef node* pnode;
pnode rt[nx];
void build(int l, int r, pnode &k)
{
k=new node();
if (l==r) return;
int md=(l+r)/2;
build(l, md ,k->l);
build(md+1, r, k->r);
}
void update(int l, int r, pnode &k, pnode p, int idx, ll vl)
{
k=new node(*p);
if (l==r) return k->f=1, k->sm=vl, void();
int md=(l+r)/2;
if (idx<=md) update(l, md, k->l, p->l, idx, vl);
else update(md+1, r, k->r, p->r, idx, vl);
k->f=k->l->f+k->r->f;
k->sm=k->l->sm+k->r->sm;
}
ll query(int l, int r, pnode k, pnode p, int key)
{
if (l==r) return k->sm-p->sm;
int md=(l+r)/2;
if (k->r->f-p->r->f>=key) return query(md+1, r, k->r, p->r, key);
else return k->r->sm-p->r->sm+query(l, md, k->l, p->l, key-k->r->f+p->r->f);
}
} p;
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]+p.query(1, n, p.rt[md], p.rt[i-1], 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());
p.build(1, n, p.rt[0]);
for (int i=1; i<=n; i++)
{
auto tmp=lower_bound(srt.begin(), srt.end(), make_pair(s[i], (ll)i))-srt.begin()+1;
p.update(1, n, p.rt[i], p.rt[i-1], tmp, s[i]);
}
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... |