fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 15e2 + 5; 
  12. const int M = 3e3 + 5; 
  13.  
  14. template<typename T>
  15. void minimize(T& a, const T& b) {
  16. 	if (b < a) a = b; 
  17. }
  18.  
  19. // pos_type = 0 -> vị trí xuất phát
  20. // pos_type = 1 -> vị trí đích
  21. // pos_type = 2 -> vị trí có tường
  22. // pos_type = 3 -> vị trí có búa
  23. // obj_type -> loại của búa/tường tại vị trí đấy
  24. struct Point {
  25. 	int pos, pos_type, obj_type; 
  26. 	bool operator<(const Point& other) const {
  27. 		return pos < other.pos;
  28. 	}
  29. };
  30.  
  31. int n, m, x;
  32. int y[N], z[N];
  33.  
  34. Point a[M]; // lưu tất cả các vị trí có trong bài
  35. int beg, goal; // index của vị trí xuất phát (điểm có toạ độ 0), và vị trí kết thúc (điểm có toạ độ x)
  36. int where[N]; // where[i] = index của búa loại i 
  37.  
  38. void precompute() {
  39. 	m = 0; 
  40. 	a[++m] = {0, 0, -1}; 
  41. 	a[++m] = {x, 1, -1};
  42. 	for (int i = 1; i <= n; i++) a[++m] = {y[i], 2, i}; 
  43. 	for (int i = 1; i <= n; i++) a[++m] = {z[i], 3, i}; 
  44.  
  45. 	sort(a + 1, a + m + 1);   
  46.  
  47. 	for (int i = 1; i <= m; i++) {
  48. 		if (a[i].pos_type == 0) beg = i; 
  49. 		if (a[i].pos_type == 1) goal = i;  
  50. 		if (a[i].pos_type == 3) where[a[i].obj_type] = i; 
  51. 	}
  52. }
  53.  
  54. // dp(l, r, end_point) = Quãng đường ngắn nhất đi đến vị trí đích khi ta đã đi qua các vị trí có index nằm trong đoạn [l, r] 
  55. //          end_point  = 0/1: ta đang ở index l, hay index r
  56. ll memo[M][M][2]; 
  57.  
  58. ll dp(int l, int r, bool end_point) {
  59. 	if (l == goal || r == goal) return 0; 
  60.  
  61. 	ll& ans = memo[l][r][end_point]; 
  62. 	if (ans != -1) return ans;  
  63.  
  64. 	ans = LINF; 
  65. 	int cur = (end_point) ? a[r].pos : a[l].pos;
  66.  
  67. 	// Mở rộng sang phải
  68. 	if (r + 1 <= m) {
  69. 		Point nxt = a[r + 1]; 
  70.  
  71. 		if (nxt.pos_type != 2) { // Đi vào vị trí không có tường
  72. 			minimize(ans, abs(cur - nxt.pos) + dp(l, r + 1, 1)); 
  73. 		}
  74. 		else { // Đi vào vị trí có tường
  75. 			int hammer_idx = where[nxt.obj_type];
  76. 			if (l <= hammer_idx && hammer_idx <= r) {
  77. 				minimize(ans, abs(cur - nxt.pos) + dp(l, r + 1, 1)); 
  78. 			}
  79. 		}
  80. 	}
  81.  
  82. 	// Mở rộng sang trái
  83. 	if (l - 1 >= 1) {
  84. 		Point nxt = a[l - 1]; 
  85.  
  86. 		if (nxt.pos_type != 2) {
  87. 			minimize(ans, abs(cur - nxt.pos) + dp(l - 1, r, 0)); 
  88. 		}
  89. 		else {
  90. 			int hammer_idx = where[nxt.obj_type]; 
  91. 			if (l <= hammer_idx && hammer_idx <= r) {
  92. 				minimize(ans, abs(cur - nxt.pos) + dp(l - 1, r, 0)); 
  93. 			}
  94. 		}
  95. 	}
  96.  
  97. 	return ans; 
  98. }
  99.  
  100. int main() {
  101. 	ios::sync_with_stdio(false); 
  102. 	cin.tie(nullptr); 	
  103. 	cin >> n >> x; 
  104. 	for (int i = 1; i <= n; i++) cin >> y[i]; 
  105. 	for (int i = 1; i <= n; i++) cin >> z[i]; 
  106.  
  107. 	precompute();   
  108.  
  109. 	memset(memo, -1, sizeof memo); 
  110.  
  111. 	ll ans = dp(beg, beg, 0); 
  112. 	if (ans == LINF) ans = -1; 
  113.  
  114. 	cout << ans << '\n';  
  115. }
Success #stdin #stdout 0.03s 144800KB
comments (?)
stdin
copy 
3 10
-2 8 -5
5 -10 3
stdout
copy 
40
https://ideone.com/h6SSLo
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!