fork download
  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 maximize(T& a, const T& b) {
  13. if (a < b) a = b;
  14. }
  15.  
  16. // Ta sẽ giải quyết bài toán theo từng hàng
  17. // Với mỗi hàng cần tính được thông tin h[j] cho mọi cột j
  18. // h[j] = độ cao của cột thứ j = độ dài đoạn con liên tiếp dài nhất kết thúc tại a(i, j) và chỉ chứa toàn số 1
  19. // Giả sử hình chữ nhật ta chọn phủ đoạn [l, r] -> chiều dài
  20. // Nhận xét: chiều rộng sẽ là min{h[l..r]}
  21. // Ở đây nếu for qua mọi đoạn [l, r] thì sẽ không đủ độ phức tạp
  22. // Nên thay vào đó ta sẽ thử cho từng h(j) làm giá trị min (1 <= j <= m)
  23. // rồi tìm đoạn [l, r] dài nhất chứa j thoả mãn h(j) là min của đoạn [l, r]
  24. // - Gọi l(j) = phần tử gần nhất bên trái < h(j)
  25. // r(j) = phần tử gần nhất bên phải < h(j)
  26. // => [l(j) + 1, r(j) - 1] chính là đoạn dài nhất chứa j thoả mãn h(j) là min
  27.  
  28. const int N = 1e3 + 5;
  29.  
  30. int n, m;
  31. int a[N][N];
  32.  
  33. int h[N];
  34. int l[N];
  35. int r[N];
  36.  
  37. int solve(int i) {
  38. for (int j = 1; j <= m; j++) {
  39. if (a[i][j] == 0) h[j] = 0;
  40. else h[j]++;
  41. }
  42.  
  43. vector<int> st;
  44. for (int j = 1; j <= m; j++) {
  45. while (!st.empty() && h[st.back()] >= h[j]) st.pop_back();
  46. l[j] = st.empty() ? 0 : st.back();
  47. st.push_back(j);
  48. }
  49.  
  50. st.clear();
  51. for (int j = m; j >= 1; j--) {
  52. while (!st.empty() && h[st.back()] >= h[j]) st.pop_back();
  53. r[j] = st.empty() ? m + 1 : st.back();
  54. st.push_back(j);
  55. }
  56.  
  57. int ans = 0;
  58. for (int j = 1; j <= m; j++) {
  59. maximize(ans, (r[j] - l[j] - 1) * h[j]);
  60. }
  61.  
  62. return ans;
  63. }
  64.  
  65. int main() {
  66. ios::sync_with_stdio(false);
  67. cin.tie(nullptr);
  68. cin >> n >> m;
  69.  
  70. for (int i = 1; i <= n; i++) {
  71. for (int j = 1; j <= m; j++) cin >> a[i][j];
  72. }
  73.  
  74. int ans = 0;
  75. for (int i = 1; i <= n; i++) {
  76. maximize(ans, solve(i));
  77. }
  78.  
  79. cout << ans << '\n';
  80. }
Success #stdin #stdout 0.01s 5296KB
stdin
11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1
stdout
49