Submission #1217345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217345		12345678	Tricks of the Trade (CEOI23_trade)	C++20	50 / 100	1165 ms	260368 KiB

trade

#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;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 5 / 10
• Subtask 3: 5 / 10
• Subtask 4: 10 / 25
• Subtask 5: 25 / 45