Submission #524708

#	Time	Username	Problem	Language	Result	Execution time	Memory
524708		Deepesson	Salesman (IOI09_salesman)	C++17	62 / 100	676 ms	52728 KiB

salesman

#include <bits/stdc++.h>
#define MAX 505000
using ll = long long;
ll inf = (1e9);
struct Seg3 {

    ll tab[MAX*4];

    void update(int t,ll k,int la=0,int ra=MAX-1,int pos=1){
        if(la>t||ra<t)return;
        if(la==ra){
            tab[pos]=std::max(tab[pos],k);
            return;
        }
        int m = (la+ra)/2;
        update(t,k,la,m,pos*2);
        update(t,k,m+1,ra,(pos*2)+1);
        tab[pos]=std::max(tab[pos*2],tab[(pos*2)+1]);
    }

    ll query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
        if(la>r||ra<l)return -inf;
        if(la>=l&&ra<=r){
            return tab[pos];
        }
        int m = (la+ra)/2;
        return std::max(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
    }

    void iniciar(void){
        for(auto&x:tab)x=-inf;
    }

};

ll U,D;
ll Q,S;
Seg3 upper,down;
typedef std::pair<ll,ll> pll;
typedef std::pair<ll,pll> plp;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    upper.iniciar();
    down.iniciar();
    std::cin>>Q>>D>>U>>S;
    upper.update(S,+(U*S));
    down.update(S,-(D*S));

    std::vector<plp> eventos;
    eventos.push_back(plp(1e9,pll(S,0)));

    for(int i=0;i!=Q;++i){
        ll D,L,X;
        std::cin>>D>>L>>X;
        eventos.push_back({D,{L,X}});
    }

    std::sort(eventos.begin(),eventos.end());
    ll last=0;
    for(auto&x:eventos){
        ll local = x.second.first;
        ll bonus = x.second.second;
        ll descer = down.query(local,MAX-1);
        ll subir = upper.query(0,local-1);
        ll ans = std::max(descer+bonus+(D*local),subir+bonus-(U*local));
        last=ans;
       /// std::cout<<"Valor desce: "<<descer-bonus+(D*local)<<"\n";
       /// std::cout<<"D: "<<descer<<" "<<"S: "<<subir<<"\n";
       /// std::cout<<"Dia "<<x.first<<" Lucro: "<<ans<<" "<<local<<"\n";
        down.update(local,ans-(D*local));
        upper.update(local,ans+(U*local));
    }
    std::cout<<last<<"\n";
}

• Subtask 1: 62 / 100