Submission #859999

#	Time	Username	Problem	Language	Result	Execution time	Memory
859999		jk410	Salesman (IOI09_salesman)	C++17	100 / 100	609 ms	30548 KiB

salesman

#include <iostream>
#include <algorithm>
#define maxx(a,b) a=max(a,b)
using namespace std;
typedef long long ll;
struct market{
    int t,l,m;
    void input(){
        cin>>t>>l>>m;
    }
};
const ll INF=(int)1e18;
const int MAX=500001;
ll update(ll *tree,int x,ll v,int l,int r,int n){
    if (r<x||x<l)
        return tree[n];
    if (l==r)
        return maxx(tree[n],v);
    int m=(l+r)>>1;
    return tree[n]=max(update(tree,x,v,l,m,n<<1),update(tree,x,v,m+1,r,n<<1|1));
}
ll query(ll *tree,int lx,int rx,int l,int r,int n){
    if (r<lx||rx<l)
        return -INF;
    if (lx<=l&&r<=rx)
        return tree[n];
    int m=(l+r)>>1;
    return max(query(tree,lx,rx,l,m,n<<1),query(tree,lx,rx,m+1,r,n<<1|1));
}
int N,U,D,S;
market A[500001];
ll TreeU[1<<20],TreeD[1<<20];
ll DPU[500001],DPD[500001];
ll queryU(int idx){
    ll umx=query(TreeU,A[idx].l,MAX,1,MAX,1);
    if (umx==-INF)
        return -INF;
    return umx+A[idx].m+(ll)U*A[idx].l;
}
ll queryD(int idx){
    ll dmx=query(TreeD,1,A[idx].l,1,MAX,1);
    if (dmx==-INF)
        return -INF;
    return dmx+A[idx].m-(ll)D*A[idx].l;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fill(TreeU+1,TreeU+(1<<20),-INF);
    fill(TreeD+1,TreeD+(1<<20),-INF);
    cin>>N>>U>>D>>S;
    for (int i=0; i<N; i++)
        A[i].input();
    A[N]={MAX,S,0};
    sort(A,A+N+1,[&](market a,market b)->bool{
        if (a.t!=b.t)
            return a.t<b.t;
        return a.l<b.l;
    });
    update(TreeU,S,-(ll)U*S,1,MAX,1);
    update(TreeD,S,(ll)D*S,1,MAX,1);
    for (int r=0,l=0; r<=N; r++){
        if (r==N||A[r+1].t!=A[r].t){
            for (int i=l; i<=r; i++)
                DPU[i]=DPD[i]=max(queryU(i),queryD(i));
            for (int i=r-1; i>=l; i--)
                maxx(DPU[i],DPU[i+1]+A[i].m-(ll)U*(A[i+1].l-A[i].l));
            for (int i=l+1; i<=r; i++)
                maxx(DPD[i],DPD[i-1]+A[i].m-(ll)D*(A[i].l-A[i-1].l));
            for (int i=l; i<=r; i++){
                update(TreeD,A[i].l,max(DPU[i],DPD[i])+(ll)D*A[i].l,1,MAX,1);
                update(TreeU,A[i].l,max(DPU[i],DPD[i])-(ll)U*A[i].l,1,MAX,1);
            }
            l=r+1;
        }
    }
    /*
    for (int i=0; i<=N; i++){
        DP[i]=-INF;
        ll umx=query(TreeU,A[i].l,MAX,1,MAX,1);
        if (umx!=-INF)
            maxx(DP[i],umx+A[i].m+(ll)U*A[i].l);
        ll dmx=query(TreeD,1,A[i].l,1,MAX,1);
        if (dmx!=-INF)
            maxx(DP[i],dmx+A[i].m-(ll)D*A[i].l);
        update(TreeU,A[i].l,DP[i]-(ll)U*A[i].l,1,MAX,1);
        update(TreeD,A[i].l,DP[i]+(ll)D*A[i].l,1,MAX,1);
    }
    cout<<DP[N];
    */
    cout<<max(DPU[N],DPD[N]);
    return 0;
}

• Subtask 1: 100 / 100