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_same[16][16];
  17. bool ok_shift[16][16]; 
  18. bool dp[1 << 16][16];    
  19.  
  20. bool check(int k) {
  21. 	// ok_same[x][y]  = Với mọi i < m, |a[x][i] - a[y][i]| >= k
  22. 	// ok_shift[x][y] = Với mọi i < m - 1, |a[x][i + 1] - a[y][i]| >= k
  23. 	for (int x = 0; x < n; x++) {
  24. 		for (int y = 0; y < n; y++) {
  25. 			ok_same[x][y] = true;
  26. 			ok_shift[x][y] = true;    
  27. 			for (int i = 0; i < m; i++) {
  28. 				ok_same[x][y] &= (abs(a[x][i] - a[y][i]) >= k); 
  29. 				if (i + 1 < m) ok_shift[x][y] &= (abs(a[x][i + 1] - a[y][i]) >= k); 
  30. 			}
  31. 		}
  32. 	}
  33.  
  34. 	for (int first_row = 0; first_row < n; first_row++) {
  35. 		// dp[mask][y] = 1 nếu tồn tại cách sắp xếp các hàng trong mask thoả ok_same 
  36. 		//                 cho mọi cặp hàng được xếp kề nhau,
  37. 		//                 với hàng đầu tiên = first_row và hàng cuối cùng = y   
  38. 		for (int mask = 0; mask < (1 << n); mask++) {
  39. 			for (int y = 0; y < n; y++) {
  40. 				bool& cur = dp[mask][y];   
  41. 				if (mask == (1 << y) && y == first_row) {
  42. 					cur = 1;  
  43. 					continue; 
  44. 				}		
  45. 				cur = 0;  
  46. 				if (!(mask & (1 << first_row))) continue; 
  47. 				if (!(mask & (1 << y))) continue; 
  48. 				for (int x = 0; x < n; x++) {
  49. 					if (ok_same[x][y]) {
  50. 						int prev_mask = mask ^ (1 << y); 
  51. 						cur |= dp[prev_mask][x]; 
  52. 					}
  53. 				}
  54. 			}
  55. 		}
  56.  
  57. 		for (int last_row = 0; last_row < n; last_row++) { 
  58. 			if (dp[(1 << n) - 1][last_row] && ok_shift[first_row][last_row]) return true; 
  59. 		}
  60. 	}
  61. 	return false; 
  62. }
  63.  
  64. int main() {
  65. 	ios::sync_with_stdio(false); 
  66. 	cin.tie(nullptr); 	
  67. 	cin >> n >> m; 
  68. 	for (int i = 0; i < n; i++) {
  69. 		for (int j = 0; j < m; j++) cin >> a[i][j]; 
  70. 	}
  71.  
  72. 	int l = 0, r = 1e9, ans = -1; 
  73. 	while (l <= r) {
  74. 		int mid = (l + r) >> 1; 
  75. 		if (check(mid)) {
  76. 			ans = mid; 
  77. 			l = mid + 1; 
  78. 		}
  79. 		else {
  80. 			r = mid - 1; 
  81. 		}
  82. 	}
  83.  
  84. 	cout << ans << '\n'; 
  85. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
4 2
9 9
10 8
5 3
4 3
stdout
copy 
5
https://ideone.com/ovFaJt
language:
C++14 (gcc 8.3)
created:
12 days 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!