mr_dot_convict

1031-Railway_tickets-Timus-mr.convict

Sep 20th, 2020 (edited)
1,210
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Hack it and have it ;) //
  2. /*author* Priyanshu Shrivastav (from IIT Palakkad) *
  3.  * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
  4.  * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
  5.  * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
  6.  * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
  7. When I wrote this, only God and I understood what I was doing
  8.  ** * * * * * * * Now, only God knows!* * * * * * */
  9. #include      <bits/stdc++.h>
  10. using namespace std;
  11. #define IOS       ios_base::sync_with_stdio(false); cin.tie (nullptr)
  12. #define PREC      cout.precision (10); cout << fixed
  13. #ifdef CONVICTION
  14. #include "/home/convict/Dropbox/myfiles/sport_coding/cplib/snippets/debug.h"
  15. #else
  16. #define debug(x...)
  17. #endif
  18. //Don’t practice until you get it right. Practice until you can’t get it wrong
  19.  
  20. void preproc()
  21. {
  22. }
  23.  
  24. void solve()
  25. {
  26.    vector <int> L(3);
  27.    vector <int> C(3);
  28.    for (int i = 0; i < 3; ++i) cin >> L[i];
  29.    for (int i = 0; i < 3; ++i) cin >> C[i];
  30.  
  31.    int N, A, B;
  32.    cin >> N >> A >> B;
  33.  
  34.    if (A > B) swap(A, B);
  35.    vector <long long> dist(N + 1);
  36.    for (int i = 2; i <= N; ++i) {
  37.       cin >> dist[i];
  38.    }
  39.  
  40.    // binary search to get the max index satisfying dist between pos and
  41.    // nxt_pos to be <= mx_len
  42.    const int D = 17;
  43.    auto give_mxidx = [&] (int pos, int mx_len) -> int {
  44.       int nxt_pos = pos;
  45.       for (int k = D; k >= 0; --k) {
  46.          if (nxt_pos + (1 << k) - 1 <= N and
  47.                dist[nxt_pos + (1 << k) - 1] - dist[pos] <= mx_len) {
  48.             nxt_pos += (1 << k);
  49.          }
  50.       }
  51.       return nxt_pos - 1;
  52.    };
  53.  
  54.    vector <bool> vis(N);
  55.    using pp = pair <long long, int>;
  56.    priority_queue <pp, vector <pp>, greater <pp>> pq;
  57.  
  58.    pq.push({0, A});
  59.  
  60.    while (!pq.empty()) {
  61.       long long len = pq.top().first;
  62.       int pos = pq.top().second;
  63.       pq.pop();
  64.  
  65.       if (vis[pos]) continue;
  66.       vis[pos] = true;
  67.  
  68.       if (pos >= B) {
  69.          cout << len << '\n';
  70.          return;
  71.       }
  72.  
  73.       // try all L1, L2, L3
  74.       for (int rot = 0; rot < 3; ++rot) {
  75.          int nxt_pos = give_mxidx (pos, L[rot]);
  76.          if (!vis[nxt_pos]) {
  77.             pq.push(make_pair(len + C[rot], nxt_pos));
  78.          }
  79.       }
  80.    }
  81.    assert(false);
  82. }
  83.  
  84. signed main()
  85. {
  86.   IOS; PREC;
  87.   preproc();
  88.  
  89.   int tc = 1;
  90.   // cin >> tc;
  91.   for (int Tt = 1; Tt <= tc; ++Tt) {
  92.     // cout << "Case #" << Tt << ": ";
  93.     solve();
  94.   }
  95.   return EXIT_SUCCESS;
  96. }
  97.  
RAW Paste Data