Submission #754288

#	Time	Username	Problem	Language	Result	Execution time	Memory
754288		bgnbvnbv	Salesman (IOI09_salesman)	C++14	60 / 100	569 ms	46524 KiB

salesman

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct node
{
    ll be ,lon;
    node ()
    {
        be=-inf;
        lon=-inf;
    }
    node operator+(const node&o)
    {
        node ans;
        ans.be=max(be,o.be);
        ans.lon=max(lon,o.lon);
        return ans;
    }
}st[4*maxN];
ll o,u,d;
void update(ll pos,ll val,ll id=1,ll l=1,ll r=o)
{
    if(l==r)
    {
        st[id].lon=val-pos*u;
        st[id].be=val+pos*d;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
node get(ll i,ll j,ll id=1,ll l=1,ll r=o)
{
    if(j<l||r<i) return node();
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
ll n,s;
struct qq
{
    ll t,l,m;
    bool operator<(const qq&o)
    {
        return t<o.t;
    }
}e[maxN];
pli a[maxN];
ll val[maxN],pre[maxN],luu[maxN];
void solve()
{
    cin >> n >> u >> d >> s;
    o=s;
    for(int i=1;i<=n;i++)
    {
        cin >> e[i].t >> e[i].l >> e[i].m;
        o=max(o,e[i].l);
    }
    sort(e+1,e+n+1);
    ll ans=0;
    update(s,0);
    for(int i=1;i<=n;i++)
    {
        ll j=i;
        while(j<=n&&e[j].t==e[i].t)
        {
            a[j-i+1]={e[j].l,e[j].m};
            j++;
        }
        sort(a+1,a+j-i+1);
        for(int k=1;k<=j-i;k++)
        {
            val[k]=max(get(a[k].fi+1,o).lon+a[k].fi*u+a[k].se,get(1,a[k].fi-1).be-a[k].fi*d+a[k].se);
            val[k]=max(val[k],-inf);
            pre[k]=pre[k-1]+a[k].se;
            luu[k]=val[k];
        }
        ll mx=-inf;
        // theo chieu cung huong
        // bat dau tai j val[j]+pre[i]-pre[j]-(a[i].fi-a[j].fi)*u=val[j]-pre[j]+a[j].fi*u+pre[i]-a[i].fi*u
        for(int k=2;k<=j-i;k++)
        {
            mx=max(mx,val[k-1]-pre[k-1]+a[k-1].fi*u);
            luu[k]=max(luu[k],pre[k]-a[k].fi*u+mx);
        }
        // nguoc huong
        // val[j]+pre[j-1]-pre[i-1]-(a[j].fi-a[i].fi)*d=val[j]+pre[j-1]-a[j].fi*d-pre[i-1]+a[i].fi*d
        mx=-inf;
        for(int k=j-i-1;k>=1;k--)
        {
            ll vv=k+1;
            mx=max(mx,val[vv]+pre[vv-1]-a[vv].fi*d);
            luu[k]=max(luu[k],-pre[k-1]+a[k].fi*d+mx);
        }
        for(int k=1;k<=j-i;k++)
        {
            if(a[k].fi<s) ans=max(ans,luu[k]-d*(s-a[k].fi));
            else ans=max(ans,luu[k]+-u*(a[k].fi-s));
            update(a[k].fi,luu[k]);
        }

        i=j-1;
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

salesman.cpp: In function 'void update(ll, ll, ll, ll, ll)':
salesman.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     ll mid=l+r>>1;
      |            ~^~
salesman.cpp: In function 'node get(ll, ll, ll, ll, ll)':
salesman.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     ll mid=l+r>>1;
      |            ~^~

• Subtask 1: 60 / 100