fork download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #pragma GCC optimize("O3")
  5. #pragma GCC target("sse4")
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9.  
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
  13.  
  14. const double PI = 4 * atan(1);
  15.  
  16. #define sz(x) (int)(x).size()
  17. #define ll long long
  18. #define ld long double
  19. #define mp make_pair
  20. #define pb push_back
  21. #define eb emplace_back
  22. #define pii pair<int, int>
  23. #define vi vector<int>
  24. #define f first
  25. #define s second
  26. #define lb lower_bound
  27. #define ub upper_bound
  28. #define all(x) x.begin(), x.end()
  29. #define vpi vector<pair<int, int>>
  30. #define vpd vector<pair<double, double>>
  31. #define pd pair<double, double>
  32.  
  33. #define f0r(i, a) for (int i = 0; i < a; i++)
  34. #define f1r(i, a, b) for (int i = a; i < b; i++)
  35.  
  36. void fast_io() {
  37.     ios_base::sync_with_stdio(0);
  38.     cin.tie(NULL);
  39.     cout.tie(NULL);
  40. }
  41. void io(string taskname) {
  42.     string fin = taskname + ".in";
  43.     string fout = taskname + ".out";
  44.     const char *FIN = fin.c_str();
  45.     const char *FOUT = fout.c_str();
  46.     freopen(FIN, "r", stdin);
  47.     freopen(FOUT, "w", stdout);
  48.     fast_io();
  49. }
  50. vi p;
  51. const int MAX = 1e3 + 5;
  52. unsigned hash_f(unsigned x) {
  53.     x = ((x >> 16) ^ x) * 0x45d9f3b;
  54.     x = ((x >> 16) ^ x) * 0x45d9f3b;
  55.     x = (x >> 16) ^ x;
  56.     return x;
  57. }
  58.  
  59. struct chash2 {
  60.     int operator()(pair<int, int> x) const { return hash_f(x.first) * 31 + hash_f(x.second); }
  61. };
  62.  
  63. unordered_map<pair<int, int>, int, chash2> dp1;
  64. gp_hash_table<pair<int, int>, int, chash2> dp;
  65. vpi states[MAX];
  66. int n;
  67. const int INF = 1e9;
  68. const int MAXL = 1e6 + 9;
  69. int loc[MAXL];
  70. int pre[MAXL];
  71. int num(int i, int j) {
  72.     if (i == 0) {
  73.         return pre[j];
  74.     } else {
  75.         return pre[j] - pre[i - 1];
  76.     }
  77. }
  78. // origin at 500000
  79. const int o = 500000;
  80. void calc(int x) {
  81.     for (auto it : states[x]) {
  82.         f0r(i, 2) {
  83.             int l = it.f;
  84.             int r = it.s;
  85.             int cur;
  86.             if (x == 0) {
  87.                 cur = o;
  88.                 dp[mp(l * 10, r)] = 0;
  89.                 dp[mp(l * 10 + 1, r)] = 0;
  90.             } else {
  91.                 if (i == 0) {
  92.                     cur = p[l + 1];
  93.                 } else {
  94.                     cur = p[r - 1];
  95.                 }
  96.             }
  97.             f0r(j, 2) {
  98.                 if (j == 0) {
  99.                     if (l >= 0) {
  100.                         int time = abs(p[l] - cur);
  101.                         int add = (n - x) * time;
  102.                         ;
  103.                         dp[mp((l - 1) * 10 + 0, r)] = min(dp[mp((l - 1) * 10 + 0, r)], add + dp[mp(l * 10 + i, r)]);
  104.                     }
  105.                 } else {
  106.                     if (r <= n - 1) {
  107.                         int time = abs(p[r] - cur);
  108.                         int add = (n - x) * time;
  109.                         dp[mp(l * 10 + 1, r + 1)] = min(dp[mp(l * 10 + 1, r + 1)], add + dp[mp(l * 10 + i, r)]);
  110.                     }
  111.                 }
  112.             }
  113.         }
  114.     }
  115. }
  116. int main() {
  117.     // io("cowrun");
  118.     cin >> n;
  119.     f0r(i, n) {
  120.         int pi;
  121.         cin >> pi;
  122.         pi += 500000;
  123.         p.eb(pi);
  124.         loc[pi] = 1;
  125.     }
  126.     f0r(i, MAXL) {
  127.         if (i == 0) {
  128.             pre[i] = loc[i];
  129.         } else {
  130.             pre[i] = pre[i - 1] + loc[i];
  131.         }
  132.     }
  133.     sort(all(p));
  134.     f0r(i, n) {
  135.         f0r(j, n) {
  136.             if (p[i] < o && o < p[j]) {
  137.                 assert(num(p[i], p[j]) - 2 >= 0);
  138.                 states[num(p[i], p[j]) - 2].eb(mp(i, j));
  139.                 dp[mp(i * 10 + 0, j)] = INF; // left
  140.                 dp[mp(i * 10 + 1, j)] = INF; // right
  141.             }
  142.         }
  143.     }
  144.     // return 0;
  145.     f1r(i, -1, n + 1) {
  146.         dp[mp(-1 * 10, i)] = INF;
  147.         dp[mp(-1 * 10 + 1, i)] = INF;
  148.         dp[mp(i * 10, n)] = INF;
  149.         dp[mp(i * 10 + 1, n)] = INF;
  150.     }
  151.     f0r(i, n) {
  152.         if (p[i] < o) {
  153.  
  154.             states[num(p[i], MAXL - 1) - 1].eb(mp(i, n));
  155.         } else {
  156.             states[num(0, p[i]) - 1].eb(mp(-1, i));
  157.         }
  158.     }
  159.     f0r(i, n + 1) { calc(i); }
  160.     cout << min(dp[mp(-1 * 10 + 1, n)], dp[mp(-1 * 10, n)]) << endl;
  161.     // cout << dp[mp(1*10+1, 4)] << endl;
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0s 23096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000
https://ideone.com/ikfX3E
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!