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 M = 1e4 + 5; 
  12.  
  13. int n, m;  
  14. int a[16][M]; 
  15.  
  16. bool ok[16][16];  
  17. bool dp[1 << 16][16]; 
  18.  
  19. bool check(int k) {
  20. 	// ok[x][y] = 1 nếu hàng y có thể đặt kề ngay phía dưới hàng x, 0 nếu ngược lại
  21. 	for (int x = 0; x < n; x++) {
  22. 		for (int y = 0; y < n; y++) {
  23. 			ok[x][y] = true;  
  24. 			for (int i = 0; i < m; i++) {
  25. 				ok[x][y] &= (abs(a[y][i] - a[x][i]) >= k); 
  26. 			}
  27. 		}
  28. 	}
  29.  
  30. 	for (int first_row = 0; first_row < n; first_row++) { // Hàng đầu tiên
  31. 		// dp[mask][last_row] = 1 nếu tồn tại một cách sắp xếp các hàng có trong tập mask, với last_row là hàng cuối cùng
  32. 		//                      sao cho thoả mãn điều kiện ok[x][y] với mọi hàng x, y được xếp kề nhau 
  33. 		//						và hàng y được xếp kề ngay phía dưới hàng x
  34. 		memset(dp, 0, sizeof dp); 
  35. 		dp[1 << first_row][first_row] = 1;
  36.  
  37. 		for (int mask = 0; mask < (1 << n); mask++) {
  38. 			for (int x = 0; x < n; x++) {
  39. 				if (dp[mask][x] == 0) continue; 
  40. 				for (int y = 0; y < n; y++) {
  41. 					if ((mask >> y) & 1) continue; 
  42. 					if (!ok[x][y]) continue; 
  43. 					int next_mask = mask | (1 << y); 
  44. 					dp[next_mask][y] = 1; 
  45. 				}
  46. 			}
  47. 		}
  48.  
  49. 		// Một cách sắp xếp thoả mãn khi thoả mãn dp = 1 (điều kiện cần)
  50. 		// và thoả thêm điều kiện của first_row và last_row (điều kiện đủ)
  51. 		for (int last_row = 0; last_row < n; last_row++) { 
  52. 			if (dp[(1 << n) - 1][last_row]) {
  53. 				bool valid = true;  
  54. 				for (int i = 0; i + 1 < m; i++) {
  55. 					if (abs(a[first_row][i + 1] - a[last_row][i]) < k) {
  56. 						valid = false;
  57. 						break; 
  58. 					}
  59. 				} 
  60. 				if (valid) return true; 
  61. 			}
  62. 		}
  63. 	}
  64.  
  65. 	return false; 
  66. }
  67.  
  68. int main() {
  69. 	ios::sync_with_stdio(false); 
  70. 	cin.tie(nullptr); 	
  71. 	cin >> n >> m; 
  72. 	for (int i = 0; i < n; i++) {
  73. 		for (int j = 0; j < m; j++) cin >> a[i][j]; 
  74. 	}
  75.  
  76. 	int l = 0, r = 1e9, ans = -1; 
  77. 	while (l <= r) {
  78. 		int mid = (l + r) >> 1; 
  79.  
  80. 		if (check(mid)) {
  81. 			ans = mid; 
  82. 			l = mid + 1; 
  83. 		}
  84. 		else {
  85. 			r = mid - 1; 
  86. 		}
  87. 	}
  88.  
  89. 	cout << ans << '\n'; 
  90. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4 2
9 9
10 8
5 3
4 3
stdout
copy 
5
https://ideone.com/gps4ri
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!