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. template<typename T>
  12. void minimize(T& a, const T& b) {
  13. 	if (b < a) a = b; 
  14. }
  15.  
  16. const int N = 1e3 + 5; 
  17.  
  18. int n, m, q;  
  19. int a[N][N]; 
  20. ll sum[N][N]; 
  21.  
  22. ll getSum(int x1, int y1, int x2, int y2) {
  23. 	return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]; 
  24. }
  25.  
  26. // Trường hợp cắt ngang
  27. ll minHorizontalCut(int x1, int y1, int x2, int y2) {
  28. 	// Tìm điểm cắt ngang x nhỏ nhất sao cho S1 >= S2
  29. 	int l = x1, r = x2 - 1, ans_x = x2;  
  30. 	while (l <= r) {
  31. 		int mid = (l + r) >> 1; 
  32. 		ll S1 = getSum(x1, y1, mid, y2), S2 = getSum(mid + 1, y1, x2, y2); 
  33.  
  34. 		if (S1 >= S2) {
  35. 			ans_x = mid;   
  36. 			r = mid - 1; 
  37. 		}
  38. 		else {
  39. 			l = mid + 1; 
  40. 		}
  41. 	}
  42.  
  43. 	ll ans = LINF; 
  44. 	if (ans_x < x2) {
  45. 		ll S1 = getSum(x1, y1, ans_x, y2), S2 = getSum(ans_x + 1, y1, x2, y2); 
  46. 		minimize(ans, S1 - S2); 
  47. 	}
  48. 	if (ans_x - 1 >= x1) { // điểm cắt ngang x lớn nhất sao cho S1 < S2
  49. 		ll S1 = getSum(x1, y1, ans_x - 1, y2), S2 = getSum(ans_x, y1, x2, y2);  
  50. 		minimize(ans, S2 - S1); 
  51. 	}
  52.  
  53. 	return ans; 
  54. }
  55.  
  56. // Trường hợp cắt dọc
  57. ll minVerticalCut(int x1, int y1, int x2, int y2) {
  58. 	// Tìm điểm cắt dọc y nhỏ nhất sao cho S1 >= S2
  59. 	int l = y1, r = y2 - 1, ans_y = y2;  
  60. 	while (l <= r) {
  61. 		int mid = (l + r) >> 1; 
  62. 		ll S1 = getSum(x1, y1, x2, mid), S2 = getSum(x1, mid + 1, x2, y2); 
  63.  
  64. 		if (S1 >= S2) {
  65. 			ans_y = mid;  
  66. 			r = mid - 1; 
  67. 		}
  68. 		else {
  69. 			l = mid + 1; 
  70. 		}
  71. 	}
  72.  
  73. 	ll ans = LINF;  
  74. 	if (ans_y < y2) {
  75. 		ll S1 = getSum(x1, y1, x2, ans_y), S2 = getSum(x1, ans_y + 1, x2, y2); 
  76. 		minimize(ans, S1 - S2);
  77. 	}
  78. 	if (ans_y - 1 >= y1) { // điểm cắt dọc y lớn nhất sao cho S1 < S2
  79. 		ll S1 = getSum(x1, y1, x2, ans_y - 1), S2 = getSum(x1, ans_y, x2, y2); 
  80. 		minimize(ans, S2 - S1); 
  81. 	}
  82.  
  83. 	return ans; 
  84. }
  85.  
  86. int main() {
  87. 	ios::sync_with_stdio(false); 
  88. 	cin.tie(nullptr); 	
  89. 	cin >> n >> m >> q;  
  90. 	for (int i = 1; i <= n; i++) {
  91. 		for (int j = 1; j <= m; j++) cin >> a[i][j]; 
  92. 	}
  93.  
  94. 	for (int x = 1; x <= n; x++) {
  95. 		for (int y = 1; y <= m; y++) {
  96. 			sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1] + a[x][y]; 
  97. 		}
  98. 	}
  99.  
  100. 	while (q--) {
  101. 		int x1, y1, x2, y2; 
  102. 		cin >> x1 >> y1 >> x2 >> y2; 
  103.  
  104. 		ll ans = min(minHorizontalCut(x1, y1, x2, y2), minVerticalCut(x1, y1, x2, y2)); 	
  105. 		cout << ans << '\n';
  106. 	}
  107. }
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin
copy 
3 3 2
1 1 1
1 1 1
1 1 1
1 1 3 3
1 1 3 2
stdout
copy 
3
0
https://ideone.com/BVAZvm
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!