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. struct chash2 {
  53.     int operator()(pair<int, int> x) const { return x.first* 31 + x.second; }
  54. };
  55. unordered_map<pair<int, int>, int, chash2> dp;
  56. gp_hash_table<pair<int, int>, int, chash2> dp1;
  57. vpi states[MAX];
  58. int n;
  59. const int INF = 1e9;
  60. const int MAXL = 1e6+ 9;
  61. int loc[MAXL];
  62. int pre[MAXL];
  63. int num(int i, int j){
  64.     if(i == 0){
  65.         return pre[j];
  66.     }
  67.     else{
  68.         return pre[j] - pre[i-1];
  69.     }
  70. }
  71. //origin at 500000
  72. const int o = 500000;
  73. void calc(int x){
  74.     for(auto it: states[x]){
  75.         f0r(i, 2){
  76.             int l = it.f;
  77.             int r = it.s;
  78.             int cur;
  79.             if(x == 0){
  80.                 cur = o;
  81.                 dp[mp(l*10, r)] = 0;
  82.                 dp[mp(l*10+1, r)] = 0;
  83.             }
  84.             else{
  85.                 if(i ==0){
  86.                     cur = p[l+1];
  87.                 }
  88.                 else{
  89.                     cur = p[r-1];
  90.                 }
  91.             }
  92.             f0r(j, 2){
  93.                 if(j == 0){
  94.                     if(l>= 0){
  95.                         int time = abs(p[l] - cur);
  96.                         int add = (n-x)* time;;
  97.                         dp[mp((l-1)*10 + 0, r)] =  min(dp[mp((l-1)*10 + 0, r)], add+ dp[mp(l*10 + i, r)]);
  98.                     }
  99.                 }
  100.                 else{
  101.                     if(r<= n-1){
  102.                         int time = abs(p[r] - cur);
  103.                         int add = (n-x)* time;
  104.                         dp[mp(l*10 + 1,  r+1)] =  min(dp[mp(l*10 + 1, r+1)], add+ dp[mp(l*10 + i, r)]);
  105.                     }
  106.                 }
  107.             }
  108.         }
  109.     }
  110. }
  111. int main(){
  112.     io("cowrun");
  113.     cin >> n;
  114.     f0r(i, n){
  115.         int pi;
  116.         cin >> pi;
  117.         pi += 500000;
  118.         p.eb(pi);
  119.         loc[pi] = 1;
  120.     }
  121.     f0r(i, MAXL){
  122.         if(i == 0){
  123.             pre[i] = loc[i];
  124.         }
  125.         else{
  126.             pre[i] = pre[i-1] + loc[i];
  127.         }
  128.     }
  129.     sort(all(p));
  130.     f0r(i, n){
  131.         f0r(j, n){
  132.             if(p[i] <o && o< p[j] ){
  133.                 assert(num(p[i], p[j]) - 2>= 0);
  134.                 states[num(p[i], p[j])-2].eb(mp(i, j));
  135.                 dp[mp(i*10+0, j)] = INF; // left
  136.                 dp[mp(i*10+1, j)] = INF; // right
  137.             }
  138.         }
  139.     }
  140.     //return 0;
  141.     f1r(i, -1, n+1){
  142.         dp[mp(-1*10, i)] = INF;
  143.         dp[mp(-1*10+1, i)] = INF;
  144.         dp[mp(i*10, n)] = INF;
  145.         dp[mp(i*10 + 1, n)] = INF;
  146.     }
  147.     f0r(i, n){
  148.         if(p[i] < o){
  149.  
  150.             states[num(p[i], MAXL-1)-1].eb(mp(i, n));
  151.         }
  152.         else{
  153.             states[num(0, p[i])-1].eb(mp(-1, i));
  154.         }
  155.     }
  156.     f0r(i, n+1){
  157.         calc(i);
  158.     }
  159.     cout << min(dp[mp(-1*10 + 1, n)], dp[mp(-1*10, n)] )<< endl;
  160.     //cout << dp[mp(1*10+1, 4)] << endl;
  161.     return 0;
  162. }
  163.  
Runtime error #stdin #stdout #stderr 0s 23088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/Id7SZM
language:
C++ (gcc 8.3)
created:
6 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!