제출 #1217342

#제출 시각아이디문제언어결과실행 시간메모리
121734212345678Tricks of the Trade (CEOI23_trade)C++20
0 / 100
435 ms260144 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...