제출 #1164144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164144		imarn	Tricks of the Trade (CEOI23_trade)	C++20	50 / 100	884 ms	254172 KiB

trade

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=3e5+5;
ll c[mxn]{0},s[mxn]{0};
ll rs=0;vector<ll>vs;
int nn,n,k;
struct node{
    int tt;ll sm;
    node*l,*r;
    node() : tt(0),sm(0),l(0),r(0){};
    node(ll x) : tt(1),sm(x),l(0),r(0){};
    node(ll x,int y) : tt(y),sm(x),l(0),r(0){};
    node(node*tl,node*tr) : tt(tl->tt+tr->tt),sm(tl->sm+tr->sm),l(tl),r(tr){};
};
node *build(int l,int r){
    if(l==r)return new node();
    int m=(l+r)>>1;
    return new node(build(l,m),build(m+1,r));
}node*rt[mxn];
node *update(node *t,int l,int r,int idx,ll v){
    if(l==r)return new node(t->sm+v,t->tt+1);
    int m=(l+r)>>1;
    if(idx<=m)return new node(update(t->l,l,m,idx,v),t->r);
    return new node(t->l,update(t->r,m+1,r,idx,v));
}
ll qr(node *tl,node *tr,int l,int r,int k){
    if(l==r){
        return min(tr->sm-tl->sm,vs[l-1]*k);
    }int m=(l+r)>>1;
    int te=tr->r->tt-tl->r->tt;
    if(te>=k)return qr(tl->r,tr->r,m+1,r,k);
    return tr->r->sm-tl->r->sm+qr(tl->l,tr->l,l,m,k-te);
}
ll ans=-1e16;
void solve(int l,int r,int opl,int opr){
    if(r<l)return;
    int m=(l+r)>>1;
    pll t={-1e16,-1};
    for(int i=opl;i<=min(m-k+1,opr);i++){
        t=max(t,{-c[m]+c[i-1]+s[m]+qr(rt[i-1],rt[m-1],1,nn,k-1),i});
    }ans=max(ans,t.f);
    if(t.s!=-1)solve(l,m-1,opl,t.s);
    else solve(l,m-1,opl,opr);
    if(t.s!=-1)solve(m+1,r,t.s,opr);
    else solve(m+1,r,opl,opr);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;for(int i=1;i<=n;i++)cin>>c[i],c[i]+=c[i-1];for(int i=1;i<=n;i++)cin>>s[i],vs.pb(s[i]);
    sort(all(vs));vs.erase(unique(all(vs)),vs.end());nn=sz(vs);
    rt[0]=build(1,nn);
    for(int i=1;i<=n;i++)rt[i]=update(rt[i-1],1,nn,ub(vs,s[i]),s[i]);
    solve(1,n,1,n);
    cout<<ans;
}

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