Submission #57634

#	Time	Username	Problem	Language	Result	Execution time	Memory
57634		Bodo171	Salesman (IOI09_salesman)	C++14	30 / 100	1085 ms	66560 KiB

salesman

#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=500005;
vector< pair<int,int> > v[nmax];
int n,m,st,dr,i,j,t,wh,prof;
long long u,d,poz,s,val,mx,k;
long long opt[nmax],gg[nmax];
struct aint
{
     long long arb[4*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);
}
long long get_opt(long long poz)
{
    long long ret=LLONG_MIN;
    mx=LLONG_MIN;st=1;dr=poz;
    A[0].query(1,1,n);
    ret=max(ret,mx-1LL*poz*d);
    mx=LLONG_MIN;st=poz;dr=n;
    A[1].query(1,1,n);
    ret=max(ret,mx+1LL*poz*u);
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>u>>d>>s;
    for(i=1;i<=n;i++)
    {
        cin>>t>>wh>>prof;
        v[t].push_back({wh,prof});
    }
    n=5*100*1000+1;
    for(i=1;i<=4*n;i++)
        A[0].arb[i]=A[1].arb[i]=LLONG_MIN/2;
    poz=s;val=0;
    recalc();
    for(i=1;i<=n;i++)
        if(v[i].size())
    {
        sort(v[i].begin(),v[i].end());
        mx=LLONG_MIN;
        for(j=0;j<v[i].size();j++)
        {
            poz=v[i][j].first;
            gg[poz]=get_opt(poz);
            k=gg[poz]+poz*d;
            if(k>mx) mx=k;
            opt[poz]=mx-poz*d+1LL*v[i][j].second;
        }
        mx=LLONG_MIN;
        for(j=v[i].size()-1;j>=0;j--)
        {
            poz=v[i][j].first;
            k=gg[poz]-poz*u;
            if(k>mx) mx=k;
            opt[poz]=max(opt[poz],mx+poz*u+1LL*v[i][j].second);
            recalc();
        }
    }
    cout<<get_opt(s);
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~

• Subtask 1: 30 / 100