Submission #885202

#TimeUsernameProblemLanguageResultExecution timeMemory
885202MatjazSalesman (IOI09_salesman)C++14
85 / 100
3094 ms41536 KiB
// // IOI2009Salesman.cpp // // // Created by Matjaz Leonardis on 11/11/2023. // #include <iostream> #include <vector> #include <algorithm> using namespace std; struct fair{ int T; int L; int M; bool operator<(const fair& other) const { return T < other.T || (T == other.T && L < other.L); } }; int N,D,U,S; int INF = (1<<31); int MAXL = 0; long long distance(int L1, int L2){ if (L1 > L2) return D * (L1 - L2); return U * (L2 - L1); } vector<int> upstream; vector<int> downstream; void insert_downstream(int x, int v){ while (x < downstream.size()){ downstream[x] = max(downstream[x], v); x += x & (-x); } } void insert_upstream(int x, int v){ x = MAXL - x + 1; while (x < upstream.size()){ upstream[x] = max(upstream[x], v); x += x & (-x); } } int best_downstream(int x){ int res = INF; while (x > 0){ res = max(res, downstream[x]); x -= x & (-x); } return res; } int best_upstream(int x){ x = MAXL - x + 1; int res = INF; while (x > 0){ res = max(res, upstream[x]); x -= x & (-x); } return res; } int main(){ cin >> N >> D >> U >> S; vector<fair> fairs(N+2); MAXL = S; for (int i=0;i<N;i++){ cin >> fairs[i].T >> fairs[i].L >> fairs[i].M; MAXL = max(MAXL, fairs[i].L); } fair start = {-1, S, 0}; fair end = {500001, S, 0}; fairs[N] = start; fairs[N+1] = end; sort(fairs.begin(), fairs.end()); vector<long long> best(N+2, 0); best[N + 1] = 0; bool distinctTimes = true; for (int i=1;i<fairs.size();i++) if (fairs[i].T == fairs[i-1].T){ distinctTimes = false; break; } vector<vector<int> > segment(1); segment[0].push_back(0); for (int i=1;i<=N+1;i++){ if (fairs[i].T != fairs[i-1].T){ segment.push_back(vector<int> ()); } segment.back().push_back(i); } if (distinctTimes){ upstream.assign(MAXL + 1, INF); downstream.assign(MAXL + 1, INF); insert_upstream(S, - S * U); insert_downstream(S, - (MAXL - S) * D); for (int i=N;i>=0;i--){ int best_remaining; best_remaining = - distance(fairs[i].L, S); int L = fairs[i].L; // Get best choice upstream and downstream adjusted for current location best_remaining = max(best_remaining, best_downstream(L) + (MAXL - L) * D); best_remaining = max(best_remaining, best_upstream(L) + L * U); best[i] = fairs[i].M + best_remaining; insert_upstream(L, best[i] - L * U); insert_downstream(L, best[i] - (MAXL - L) * D); } } else { int last_finished = N + 2; for (int x=segment.size()-1;x>=0;x--){ for (int y=segment[x].size() - 1; y>=0; y--){ int i = segment[x][y]; long long best_remaining; if (i == N + 1) best_remaining = 0; else best_remaining = -distance(fairs[i].L, S); for (int j=last_finished;j<=N+1;j++){ best_remaining = max(best_remaining, -distance(fairs[i].L,fairs[j].L) + best[j]); } best[i] = fairs[i].M + best_remaining; } vector<long long> V(segment[x].size()); vector<int> Ls(segment[x].size()); vector<int> Ms(segment[x].size()); for(int y=0;y<segment[x].size();y++){ V[y] = best[segment[x][y]]; Ls[y] = fairs[segment[x][y]].L; Ms[y] = fairs[segment[x][y]].M; } int i = segment[x][0] - 1; for (int j=0;j<V.size();j++){ long long accumulation = Ms[j]; for (int k=j-1;k>=0;k--){ best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(Ls[j], Ls[k])); accumulation += Ms[k]; } accumulation = Ms[j]; for (int k= j+1;k<V.size();k++){ best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(Ls[j], Ls[k])); accumulation += Ms[k]; } } last_finished = segment[x][0]; } } cout << best[0] << endl; return 0; }

Compilation message (stderr)

salesman.cpp: In function 'void insert_downstream(int, int)':
salesman.cpp:37:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (x < downstream.size()){
      |            ~~^~~~~~~~~~~~~~~~~~~
salesman.cpp: In function 'void insert_upstream(int, int)':
salesman.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (x < upstream.size()){
      |            ~~^~~~~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i=1;i<fairs.size();i++) if (fairs[i].T == fairs[i-1].T){
      |                  ~^~~~~~~~~~~~~
salesman.cpp:165:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             for(int y=0;y<segment[x].size();y++){
      |                         ~^~~~~~~~~~~~~~~~~~
salesman.cpp:173:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |             for (int j=0;j<V.size();j++){
      |                          ~^~~~~~~~~
salesman.cpp:185:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |                 for (int k= j+1;k<V.size();k++){
      |                                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...