제출 #871598

#제출 시각아이디문제언어결과실행 시간메모리
871598MatjazSalesman (IOI09_salesman)C++14
19 / 100
3099 ms22868 KiB
// // IOI2009Salesman.cpp // // // Created by Matjaz Leonardis on 11/11/2023. // #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> L; vector<int> T; vector<int> M; int N,D,U,S; long long distance(int L1, int L2){ if (L1 > L2) return D * (L1 - L2); return U * (L2 - L1); } int main(){ cin >> N >> D >> U >> S; vector<pair<int, pair<int,int> > > tmp(N+2); for (int i=0;i<N;i++){ cin >> tmp[i].first >> tmp[i].second.first >> tmp[i].second.second; } tmp[N] = make_pair(-1, make_pair(S, 0)); tmp[N+1] = make_pair(500001, make_pair(S, 0)); sort(tmp.begin(), tmp.end()); L.assign(N+2, 0); M.assign(N+2, 0); for (int i=0;i<N+2;i++){ L[i] = tmp[i].second.first; M[i] = tmp[i].second.second; } vector<long long> best(N+2, 0); for (int i=N+1;i>=0;i--){ long long best_remaining; if (i == N + 1) best_remaining = 0; else best_remaining = -distance(L[i], S); for (int j=i+1;j<N+1;j++){ best_remaining = max(best_remaining, -distance(L[i],L[j]) + best[j]); } best[i] = M[i] + best_remaining; } cout << best[0] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...