SHARE
TWEET

Untitled

a guest Jul 23rd, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <random>
  3.  
  4. using namespace std;
  5.  
  6. typedef unsigned long long ull;
  7. typedef long long ll;
  8. typedef long double ld;
  9. #define int ll
  10. //#define int __int128
  11. //#define ll __int128
  12. typedef pair<int, int> pii;
  13. typedef pair<ll, ll> pll;
  14. typedef vector<int> vi;
  15. typedef vector< vi > vvi;
  16. typedef vector< vvi > vvvi;
  17. typedef vector<short> vs;
  18. typedef vector<vs> vvs;
  19. typedef vector<vvs> vvvs;
  20. typedef vector<ll> vl;
  21. typedef vector<vl> vvl;
  22. typedef vector<vvl> vvvl;
  23. typedef vector<ld> vld;
  24. typedef vector<vld> vvld;
  25. typedef vector<vvld> vvvld;
  26. typedef vector<string> vst;
  27. typedef vector<vst> vvst;
  28. typedef pair<ld, ld> pld;
  29. typedef complex<double> base;
  30.  
  31. #define inmin(a, b) a = min(a, (b))
  32. #define inmax(a, b) a = max(a, (b))
  33. #define ALL(a) a.begin(),a.end()
  34. #define RALL(a) a.rbegin(),a.rend()
  35. #define sqr(x) ((x) * (x))
  36. #define fori(i, n) for(int i = 0; i < int(n); ++i)
  37. #define SZ(a) ((int)((a).size()))
  38. #define triple(T) tuple<T, T, T>
  39. #define quad(T) tuple<T, T, T, T>
  40. #define watch(x) cerr << (#x) << " = " << (x) << endl;
  41.  
  42. const double PI = 2 * acos(0.0);
  43. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  44. mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
  45.  
  46. const string DIGITS = "0123456789";
  47. const string ALPH = "abcdefghijklmnopqrstuvwxyz";
  48.  
  49. template <class T0, class T1>
  50. inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
  51.     return out << "{" << a.first << ", " << a.second << "}";
  52. }
  53.  
  54. template <class T0, class T1, class T2>
  55. inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
  56.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
  57. }
  58.  
  59. template <class T0, class T1, class T2, class T3>
  60. inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
  61.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
  62. }
  63.  
  64. template<class T>
  65. inline ostream & operator << (ostream &out, vector<T> &a) {
  66.     out << "[";
  67.     fori (i, a.size())
  68.         out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
  69.     return out;
  70. }
  71.  
  72. void smain();
  73.  
  74. signed main() {
  75.     ios::sync_with_stdio(0);
  76.     cin.tie(0); cout.tie(0);
  77.  
  78. #ifdef RUS_HOME
  79.     freopen("input.txt", "r", stdin);
  80.     //freopen("output.txt", "w", stdout);
  81.     clock_t start = clock();
  82. #else
  83.     //freopen("bubbles.in", "r", stdin);
  84.     //freopen("bubbles.out", "w", stdout);
  85. #endif
  86.     cout << setprecision(12) << fixed;
  87.     smain();
  88. #ifdef RUS_HOME
  89.     cout << "\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
  90. #endif
  91. }
  92. const int oo = 1e18 + 100;
  93. const int N = 5e6, M = 150 * 150, K = 150, ALPHA = 256, LOG = 21;
  94. int MOD = 1e9 + 7;
  95.  
  96.  
  97.  
  98. void smain() {
  99.  
  100.     int n;
  101.     cin >> n;
  102.     vi a(n), b(n);
  103.     for (int i = 0; i < n; i++)
  104.         cin >> b[i];
  105.  
  106.     for (int i = 0; i < n; i++)
  107.         cin >> a[i];
  108.  
  109.     vvi dp(n, vi(2, oo));
  110.  
  111.     dp[0][0] = 0;
  112.     dp[0][1] = abs(a[0] - b[0]);
  113.     for (int i = 1; i < n; i++) {
  114.         if (a[i] <= a[i - 1]) {
  115.             inmin(dp[i][0], dp[i - 1][0]);
  116.             inmin(dp[i][1], dp[i - 1][0] + abs(a[i] - b[i]));
  117.         }
  118.         if (b[i] >= b[i - 1]) {
  119.             inmin(dp[i][1], dp[i - 1][1]);
  120.             inmin(dp[i][0], dp[i - 1][1] + abs(a[i] - b[i]));
  121.         }
  122.         if (a[i] > a[i - 1] && b[i] < b[i - 1]) {
  123.             cout << -1;
  124.             return;
  125.         }
  126.     }
  127.  
  128.  
  129.     cout << dp[n - 1][0];
  130.  
  131.  
  132. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top