제출 #53612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53612		Diuven	Salesman (IOI09_salesman)	C++11	52 / 100	1097 ms	22908 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=1e9, XMX=500001;

int n, d, u, s;
struct shop {
    int t, x, a;
} S[MX];

inline int _max(int x, int y){
    return x<y ? y : x;
}

struct Seg {
    int tree[1100000], n;
    void init(int sz){
        n=sz;
        for(int i=1; i<1100000; i++) tree[i]=-inf;
    }
    void upt(int v, int s, int e, int pos, int val){
        if(pos<s || e<pos) return;
        if(s==e){
            tree[v]=val;
            return;
        }
        upt(v*2,s,(s+e)/2,pos,val);
        upt(v*2+1,(s+e)/2+1,e,pos,val);
        tree[v]=_max(tree[v*2], tree[v*2+1]);
    }
    void upt(int pos, int val){
        upt(1,1,n,pos,val);
    }
    int mx(int v, int s, int e, int l, int r){
        if(r<s || e<l) return -inf;
        if(l<=s && e<=r) return tree[v];
        return _max(mx(v*2,s,(s+e)/2,l,r), mx(v*2+1,(s+e)/2+1,e,l,r));
    }
    int mx(int l, int r){
        if(r<l) return -inf;
        return mx(1,1,n,l,r);
    }
} US, DS;

int D[MX];

void upt(int pos, int val){
    D[pos]=val;
    US.upt(pos, val-u*(XMX-pos));
    DS.upt(pos, val-d*(pos));
}

int get(int x){
    int upmx=US.mx(1,x), dnmx=DS.mx(x,XMX);
    upmx+=u*(XMX-x);
    dnmx+=d*(x);
    return _max(upmx, dnmx);
}

int T[MX];
int X[MX], Y[MX];
void solve(int l, int r){
    for(int i=l; i<=r; i++)
        T[i]=get(S[i].x);
    X[l]=T[l]+S[l].a;
    for(int i=l+1; i<=r; i++)
        X[i]=_max(X[i-1]-d*(S[i].x-S[i-1].x), T[i])+S[i].a;
    for(int i=r-1; i>=l; i--)
        X[i]=_max(X[i], X[i+1]-u*(S[i+1].x-S[i].x));
    
    Y[r]=T[r]+S[r].a;
    for(int i=r-1; i>=l; i--)
        Y[i]=_max(Y[i+1]-u*(S[i+1].x-S[i].x), T[i])+S[i].a;
    for(int i=l+1; i<=r; i++)
        Y[i]=_max(Y[i-1]-d*(S[i].x-S[i-1].x), T[i]);
    for(int i=l; i<=r; i++)
        upt(S[i].x, _max(X[i], Y[i]));
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>u>>d>>s;
    for(int i=1; i<=n; i++){
        int t,x,a;
        cin>>t>>x>>a;
        S[i]={t,x,a};
    }
    sort(S+1, S+n+1, [](shop &a, shop &b){
        if(a.t==b.t) return a.x<b.x;
        return a.t<b.t;
    });
    DS.init(500001);
    US.init(500001);
    for(int i=1; i<=n; i++)
        upt(i,-inf);
    upt(s, 0);
    int pos=1;
    while(pos<=n){
        int l=pos, r=pos;
        while(r<n && S[r+1].x==S[l].x) r++;
        solve(l,r);
        pos=r+1;
    }
    cout<<get(s);
    return 0;
}

• Subtask 1: 52 / 100