Submission #1020448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020448		boyliguanhan	Salesman (IOI09_salesman)	C++17	100 / 100	1047 ms	65536 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
int U,D;
#define N 500100
struct fenwicktree{
    int active=0;
    int T[N];
    vector<pair<int,int>>done;
    void upd(int n,int v){
        for(;n<N;n+=n&-n)
            done.push_back({n,T[n]}),T[n]=max(T[n],v);
    }
    int query(int n){
        int ans=-1e9;
        while(n)
            ans=max(ans,T[n]),n-=n&-n;
        return ans;
    }
    void tog(){
        if(active) {
            reverse(done.begin(),done.end());
            for(auto[x,v]:done)
                T[x]=v;
        }
        active^=1;
        done.clear();
    }
    fenwicktree(){for(auto&i:T)i=-2e9;}
} up,dn;
void dostuf(int pos,int v){
    up.upd(pos,v+pos*D);
    dn.upd(N-pos,v-pos*U);
}
int getans(int pos){
    return max(up.query(pos)-pos*D,
            dn.query(N-pos)+pos*U);
}
void tog(){
    up.tog(),dn.tog();
}
map<int,vector<pair<int,int>>>stuff;
int bst[N];
int main(){
    int n,p;
    cin>>n>>U>>D>>p;
    for(int i=1;i<=n;i++){
        int t,l,m; cin>>t>>l>>m;
        stuff[t].push_back({l,m});
    }
    dostuf(p,0);
    for(auto[day,kirby]:stuff){
        tog();
        sort(kirby.begin(),kirby.end());
        for(auto[x,y]:kirby)
            dostuf(x,bst[x]=getans(x)+y);
        tog();
        tog();
        reverse(kirby.begin(),kirby.end());
        for(auto[x,y]:kirby)
            bst[x]=max(bst[x],getans(x)+y),
            dostuf(x,getans(x)+y);
        tog();
        for(auto[x,y]:kirby)
            dostuf(x,bst[x]);
    }
    cout<<getans(p);
}

• Subtask 1: 100 / 100