Submission #1217331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217331		12345678	Tricks of the Trade (CEOI23_trade)	C++20	0 / 100	675 ms	206316 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 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 (r==0) return 0;
        if (l==0) l=1;
        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-d[i].f[idxl], idxr-d[i].f[idxr], 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;
}

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