Advertisement
Guest User

Untitled

a guest
Feb 18th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.35 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7. ll x, y, x2, y2;
  8. ll n;
  9. char a[100010];
  10. ll col[1010];
  11. ll chi[100][100010];
  12. ll ans = 0;
  13. ll tx[100010], ty[100010];
  14.  
  15. int main()
  16. {
  17. ios_base::sync_with_stdio(0);
  18. cin.tie(0);
  19.  
  20. cin >> x >> y;
  21. cin >> x2 >> y2;
  22. cin >> n;
  23. for (int i = 1; i <= n; ++i) cin >> a[i];
  24. ll dx = x2 - x, dy = y2 - y;
  25. ll lx = 0, ly = 0;
  26. for (int i = 1; i <= n; ++i)
  27. {
  28. if (a[i] == 'L') --lx;
  29. if (a[i] == 'R') ++lx;
  30. if (a[i] == 'U') ++ly;
  31. if (a[i] == 'D') --ly;
  32. tx[i] = lx;
  33. ty[i] = ly;
  34. }
  35. ll l = 0, r = 1e18;
  36. while (r - l > 1)
  37. {
  38. ll m = (r + l) / 2;
  39. ll k = m / n;
  40. if (abs(dx - tx[n] * k - tx[m % n]) + abs(dy - ty[n] * k - ty[m % n]) > m)
  41. {
  42. l = m;
  43. } else
  44. {
  45. r = m;
  46. }
  47. }
  48. ll m = l;
  49. ll k = m / n;
  50. if (abs(dx - tx[n] * k - tx[m % n]) + abs(dy - ty[n] * k - ty[m % n]) > m)
  51. {
  52. m = r;
  53. ll k = m / n;
  54. if (abs(dx - tx[n] * k - tx[m % n]) + abs(dy - ty[n] * k - ty[m % n]) > m)
  55. {
  56. cout << -1;
  57. } else
  58. {
  59. cout << r;
  60. }
  61. } else
  62. {
  63. cout << l;
  64. }
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement