Submission #57646

#TimeUsernameProblemLanguageResultExecution timeMemory
57646Bodo171Salesman (IOI09_salesman)C++14
12 / 100
1087 ms43816 KiB
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LLONG;
const LLONG nmax=500005;
LLONG n,m,st,dr,i,j,t,wh,prof;
LLONG u,d,poz,s,val,mx,k,p,nr,sum,maxi;
LLONG opt[nmax],gg[nmax];
struct tr
{
    LLONG t,first,second;
}v[nmax];
bool comp(tr unu,tr doi)
{
    if(unu.t==doi.t&&unu.first==doi.first) return unu.second<doi.second;
    if(unu.t==doi.t)return unu.first<doi.first;
    return unu.t<doi.t;
}
struct aint
{
     LLONG arb[3*nmax];
     void update(LLONG nod,LLONG l,LLONG r)
     {
         arb[nod]=max(arb[nod],val);
         if(l==r) return;
         LLONG m=(l+r)/2;
         if(poz<=m) update(2*nod,l,m);
         else update(2*nod+1,m+1,r);
     }
     void query(LLONG nod,LLONG l,LLONG r)
     {
         if(st<=l&&r<=dr)
         {
             mx=max(arb[nod],mx);
             return;
         }
         LLONG m=(l+r)/2;
         if(st<=m) query(2*nod,l,m);
         if(m<dr) query(2*nod+1,m+1,r);
     }
}A[2];
//upstream la stanga
//downstream la dreapta
void recalc()
{
    val=opt[poz]+poz*d;
    A[0].update(1,1,n);
    val=opt[poz]-poz*u;
    A[1].update(1,1,n);
}
LLONG get_opt(LLONG poz)
{
    LLONG ret=LLONG_MIN;
    mx=LLONG_MIN;st=1;dr=poz;
    A[0].query(1,1,n);
    if(mx!=LLONG_MIN)ret=max(ret,mx-poz*d);
    mx=LLONG_MIN;st=poz;dr=n;
    A[1].query(1,1,n);
    if(mx!=LLONG_MIN)ret=max(ret,mx+poz*u);
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>u>>d>>s;
    for(i=1;i<=n;i++)
    {
        ++nr;
        cin>>v[i].t>>v[i].first>>v[i].second;
    }
    n=5*100*1000+1;
    for(i=1;i<=3*n;i++)
        A[0].arb[i]=A[1].arb[i]=LLONG_MIN;
    poz=s;val=0;
    recalc();
    sort(v+1,v+nr+1,comp);
    for(i=1;i<=nr;i++)
    {
        p=i;
        while(p<=nr&&v[i].t==v[p].t)
            p++;
        p--;
        maxi=LLONG_MIN;sum=0;
        for(j=i;j<=p;j++)
        {
            poz=v[j].first;
            gg[poz]=get_opt(poz);
            k=gg[poz]+poz*d-sum;
            if(k>maxi) maxi=poz;
            sum+=v[j].second;
            opt[poz]=maxi-poz*d+sum;
        }
        maxi=LLONG_MIN;sum=0;
        for(j=p;j>=i;j--)
        {
            poz=v[j].first;
            k=gg[poz]-poz*u-sum;
            if(k>maxi) maxi=k;
            sum+=v[j].second;
            opt[poz]=max(opt[poz],maxi+poz*u+sum);
            recalc();
        }
        i=p;
    }
    cout<<get_opt(s);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...