제출 #885136

#제출 시각아이디문제언어결과실행 시간메모리
885136MatjazSalesman (IOI09_salesman)C++14
14 / 100
3098 ms24856 KiB
// // SalesmanIOI2009multiple.cpp // // // Created by Matjaz Leonardis on 09/12/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()); T.assign(N+2, 0); 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; T[i] = tmp[i].first; } 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); if (T[i] != T[i+1]){ vector<int> V; vector<int> Ls; vector<int> Ms; int index = i + 1; while (T[i+1] == T[index]){ V.push_back(best[index]); Ls.push_back(L[index]); Ms.push_back(M[index]); index++; } for (int j=0;j<V.size();j++){ int accumulation = M[j]; for (int k=j-1;k>=0;k--){ best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(L[j], L[k])); accumulation += M[k]; } accumulation = M[j]; for (int k= j+1;k<V.size();k++){ best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(L[j], L[k])); accumulation += M[k]; } } } for (int j=i+1;j<N+1;j++){ if (T[j] == T[i]) continue; best_remaining = max(best_remaining, -distance(L[i],L[j]) + best[j]); } best[i] = M[i] + best_remaining; } cout << best[0] << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

salesman.cpp: In function 'int main()':
salesman.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for (int j=0;j<V.size();j++){
      |                          ~^~~~~~~~~
salesman.cpp:78:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for (int k= j+1;k<V.size();k++){
      |                                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...