Submission #57638

#	Time	Username	Problem	Language	Result	Execution time	Memory
57638		Bodo171	Salesman (IOI09_salesman)	C++14	15 / 100	1086 ms	66560 KiB

salesman

#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=500005;
const int lim=530000;
int n,m,st,dr,i,j,t,wh,prof;
long long u,d,poz,s,val,mx,k,p,nr;
long long opt[nmax],gg[nmax];
struct tr
{
    int 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
{
     long long arb[lim+10];
     void update(int nod,int l,int r)
     {
         arb[nod]=max(arb[nod],val);
         if(l==r) return;
         int m=(l+r)/2;
         if(poz<=m) update(2*nod,l,m);
         else update(2*nod+1,m+1,r);
     }
     void query(int nod,int l,int r)
     {
         if(st<=l&&r<=dr)
         {
             mx=max(arb[nod],mx);
             return;
         }
         int 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);
}
long long get_opt(long long poz)
{
    long long ret=INT_MIN;
    mx=INT_MIN;st=1;dr=poz;
    A[0].query(1,1,n);
    ret=max(ret,mx-poz*d);
    mx=INT_MIN;st=poz;dr=n;
    A[1].query(1,1,n);
    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<=lim;i++)
        A[0].arb[i]=A[1].arb[i]=LLONG_MIN/2;
    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--;
        mx=INT_MIN;
        for(j=i;j<=p;j++)
        {
            poz=v[j].first;
            gg[poz]=get_opt(poz);
            k=gg[poz]+poz*d;
            if(k>mx) mx=k;
            opt[poz]=mx-poz*d+1LL*v[j].second;
        }
        mx=INT_MIN;
        for(j=p;j>=i;j--)
        {
            poz=v[j].first;
            k=gg[poz]-poz*u;
            if(k>mx) mx=k;
            opt[poz]=max(opt[poz],mx+poz*u+v[j].second);
            recalc();
        }
        i=p;
    }
    cout<<get_opt(s);
    return 0;
}

• Subtask 1: 15 / 100