Submission #432936

#	Time	Username	Problem	Language	Result	Execution time	Memory
432936		jhnah917	Salesman (IOI09_salesman)	C++14	15 / 100	40 ms	972 KiB

salesman

#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];
}

• Subtask 1: 15 / 100