Submission #859944

#	Time	Username	Problem	Language	Result	Execution time	Memory
859944		jk410	Salesman (IOI09_salesman)	C++17	60 / 100	550 ms	35412 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 DP[500001];
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{
        return a.t<b.t;
    });
    update(TreeU,S,-(ll)U*S,1,MAX,1);
    update(TreeD,S,(ll)D*S,1,MAX,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];
    return 0;
}

• Subtask 1: 60 / 100