fork download
  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> dp1;
  56. gp_hash_table<pair<int, int>, int, chash2> dp;
  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 23096KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error