fork download
  1. #pragma GCC target ("avx2")
  2. #pragma GCC optimization ("O3")
  3. #pragma GCC optimization ("unroll-loops")
  4. #include <cstdio>
  5. #include <numeric>
  6. #include <cmath>
  7. #include <assert.h>
  8. #include <deque>
  9. #include <iostream>
  10. #include <queue>
  11. #include <string.h>
  12. #include <set>
  13. #include <algorithm>
  14. #include <map>
  15. #include <vector>
  16. #include <bitset>
  17. #include <array>
  18. #define loop(i, n) for (int i = 0; i < n; i++)
  19. #define testcase int _t; cin >> _t; while (_t--)
  20. #define all(x) (x).begin(), (x).end()
  21. using i64 = long long;
  22. using namespace std;
  23.  
  24. void yes(bool y) {
  25. cout << (y ? "Yes\n" : "No\n");
  26. }
  27.  
  28. template<typename T>
  29. ostream& operator<<(ostream& os, vector<T> const &v) {
  30. for (T x: v) {
  31. os << x << ' ';
  32. }
  33. cout << '\n';
  34. return os;
  35. }
  36.  
  37. template<typename T>
  38. istream& operator>>(istream& is, vector<T> &v) {
  39. for (T &x: v) {
  40. is >> x;
  41. }
  42. return is;
  43. }
  44.  
  45. const int maxn = 1e6;
  46.  
  47. int n, m, g, r;
  48. vector<int> d;
  49. bitset<int(1e4 * 2000 * 2)> vis;
  50.  
  51. inline auto idx(array<i64, 3> x) {
  52. return x[1] * (g + r) + x[2];
  53. }
  54.  
  55. i64 bfs() {
  56. priority_queue< array<i64, 3> > q;
  57. q.push({0, 0, 0});
  58.  
  59. while (!q.empty()) {
  60. auto tup = q.top(); q.pop();
  61. i64 &dist = tup[0];
  62. i64 &line = tup[1];
  63. i64 &secs = tup[2];
  64. auto i = idx(tup);
  65.  
  66. if (vis[i]) continue;
  67. vis[i] = 1;
  68.  
  69. if (line == m - 1) {
  70. return dist;
  71. }
  72.  
  73. if (secs == g) { // wait for next go
  74. int cost = r;
  75. array<i64, 3> nxt = {dist + cost, line, 0};
  76. q.push(nxt);
  77. }
  78. if (line + 1 < m) {
  79. int cost = d[line + 1] - d[line];
  80. if (secs + cost <= g) {
  81. array<i64, 3> nxt = {dist + cost, line + 1, secs + cost};
  82. q.push(nxt);
  83. }
  84. }
  85. if (line - 1 >= 0) {
  86. int cost = d[line] - d[line - 1];
  87. if (secs + cost <= g) {
  88. array<i64, 3> nxt = {dist + cost, line - 1, secs + cost};
  89. q.push(nxt);
  90. }
  91. }
  92. }
  93. return -1;
  94. }
  95.  
  96. int main() {
  97. ios_base::sync_with_stdio(false);
  98. cin.tie(NULL);
  99. cin >> n >> m;
  100. d.resize(m);
  101. cin >> d;
  102. cin >> g >> r;
  103. sort(all(d));
  104. cout << bfs() << '\n';
  105. }
Success #stdin #stdout 0s 4516KB
stdin
Standard input is empty
stdout
-1