Submission #1215250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215250		Ariadna	Salesman (IOI09_salesman)	C++20	21 / 100	3096 ms	15996 KiB

salesman

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

int n, u, d, s;

struct Fair {
    int t, l, m;
};  
bool comp(Fair A, Fair B) {
    return A.t < B.t;
}

int price(int a, int b) {
    return max((b-a)*d, (b-a)*u);
}

signed main() {
    cin >> n >> u >> d >> s;
    u*=-1;

    vector<Fair> fairs(n);
    for (int i = 0; i < n; ++i) cin >> fairs[i].t >> fairs[i].l >> fairs[i].m;
    sort(fairs.begin(), fairs.end(), comp);

    vector<int> dp(n);

    for (int i = n-1; i >= 0; --i) {
        dp[i] += fairs[i].m;
        int aux = -price(fairs[i].l, s);
        for (int j = n-1; j > i; --j) {
            aux = max(aux, dp[j]-price(fairs[i].l, fairs[j].l));
        }
        dp[i] += aux;
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) ans = max(ans, dp[i]-price(s, fairs[i].l));
    cout << ans << endl;

    return 0;
}

• Subtask 1: 21 / 100