Submission #432936

#TimeUsernameProblemLanguageResultExecution timeMemory
432936jhnah917Salesman (IOI09_salesman)C++14
15 / 100
40 ms972 KiB
#include <bits/stdc++.h>
using namespace std;

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[5050];
Info A[5050];

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;
    for(int i=1; i<=N; i++){
        for(int j=0; j<i; j++){
            int unitCost = A[j].l < A[i].l ? D : U, dist = abs(A[j].l - A[i].l);
            DP[i] = max(DP[i], DP[j] + A[i].m - unitCost * dist);
        }
    }
    cout << DP[N];
}
#Verdict Execution timeMemoryGrader output
Fetching results...