제출 #1323832

#제출 시각아이디문제언어결과실행 시간메모리
1323832hectormedranoSalesman (IOI09_salesman)C++20
19 / 100
3096 ms27600 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, U, D, S;

struct fair{
    ll t = 0;
    ll m = 0;
    ll l = 0;
};

bool ord(fair f1, fair f2){
    if(f1.t != f2.t){return (f1.t < f2.t);}
    return (f1.l < f2.l);
}

ll dis(ll x, ll y){
    //cout<<x<<" "<<y<<" ";
    if(x < y){return D*(y-x);}
    else{return U*(x-y);}
}

int main() {
	cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin>>N>>U>>D>>S;
    fair HM;
    HM.l = S;
    vector<fair> F(N+1, HM);
    vector<ll> DP(N+2);
    for(ll i=1;i<=N;i++){
        cin>>F[i].t>>F[i].l>>F[i].m;
    }
    sort(F.begin(), F.end(), ord);
    F.push_back(HM);
    DP[0] = 0;
    //cout<<F[0].l<<" "<<F[N+1].l<<endl;
    for(ll i=1;i<=N+1;i++){
        DP[i] = -1e18;
        //cout<<"Para calcular DP de "<<i<<endl;
        for(ll j=0;j<i;j++){
            //cout<<DP[j]<<" - "<<dis(F[j].l, F[i].l)<<" + "<<F[i].m<<endl;
            DP[i] = max(DP[i], DP[j] - dis(F[j].l, F[i].l) + F[i].m);
        }
    }
    cout<<DP[N+1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...