Submission #432956

#	Time	Username	Problem	Language	Result	Execution time	Memory
432956		jhnah917	Salesman (IOI09_salesman)	C++14	60 / 100	487 ms	24928 KiB

salesman

#include <bits/stdc++.h>
using namespace std;

constexpr int SZ = 1 << 19;
struct SegmentTree{
    int T[SZ << 1];
    SegmentTree(){ memset(T, 0xc0, sizeof T); }
    void update(int x, int v){
        x |= SZ; T[x] = max(T[x], v);
        while(x >>= 1) T[x] = max(T[x], v);
    }
    int query(int l, int r){
        l |= SZ; r |= SZ; int ret = T[0];
        while(l <= r){
            if(l & 1) ret = max(ret, T[l++]);
            if(~r & 1) ret = max(ret, T[r--]);
            l >>= 1; r >>= 1;
        }
        return ret;
    }
};

struct Info{
    int t, l, m; // time, location, money
    bool operator < (const Info &info) const {
        return t < info.t;
    }
};

int N, U, D, S, DP[505050];
Info A[505050];

SegmentTree T_D, T_U;

void Update(int idx){
    T_D.update(A[idx].l, DP[idx] + D * A[idx].l);
    T_U.update(A[idx].l, DP[idx] - U * A[idx].l);
}

int Query(int idx){
    int dw = T_D.query(0, A[idx].l) - D * A[idx].l + A[idx].m;
    int up = T_U.query(A[idx].l, 505050) + U * A[idx].l + A[idx].m;
    return max(dw, up);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> U >> D >> S;
    for(int i=1; i<=N; i++) cin >> A[i].t >> A[i].l >> A[i].m;
    A[0] = {0, S, 0};        // start
    A[++N] = {505050, S, 0}; // end
    sort(A+1, A+N+1);

    memset(DP, 0xc0, sizeof DP);
    DP[0] = 0; Update(0);
    for(int i=1; i<=N; i++){
        DP[i] = Query(i);
        Update(i);
    }
    cout << DP[N];
}

• Subtask 1: 60 / 100