제출 #57649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57649		Bodo171	Salesman (IOI09_salesman)	C++14	100 / 100	970 ms	22288 KiB

salesman

#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
typedef int INT;
const INT nmax=500005;
INT n,m,st,dr,i,j,t,wh,prof;
INT u,d,poz,s,val,mx,k,p,nr,sum,maxi;
INT 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
{
     INT arb[3*nmax];
     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);
}
INT get_opt(INT poz)
{
    INT ret=INT_MIN;
    mx=INT_MIN;st=1;dr=poz;
    A[0].query(1,1,n);
    if(mx!=INT_MIN)ret=max(ret,mx-poz*d);
    mx=INT_MIN;st=poz;dr=n;
    A[1].query(1,1,n);
    if(mx!=INT_MIN)ret=max(ret,mx+poz*u);
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    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]=INT_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=INT_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=k;
            sum+=v[j].second;
            opt[poz]=maxi-poz*d+sum;
        }
        maxi=INT_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;
}

• Subtask 1: 100 / 100