QBRECT - Hình chữ nhật 0 1
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N];
int h[N];
int c[N][N];
int n, m;
struct Rectangle {
int h, w;
} s[N];
int size;
int main() {
ios::sync_with_stdio(false);
cin >> m >> n;
for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) h[j] = a[i][j] ? h[j] + 1 : 0;
for (int j = 0; j <= n + 1; ++j) {
int w = 0;
while (size > 0 && s[size].h >= h[j]) {
int cur_h = max(s[size - 1].h, h[j]);
w += s[size].w;
++c[cur_h + 1][w];
--c[s[size].h + 1][w];
--size;
}
++size;
s[size].w = w + 1;
s[size].h = h[j];
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) c[i + 1][j] += c[i][j];
int c1 = 0, c2 = 0;
for (int j = n; j >= 1; --j) {
c1 += c[i][j];
c2 += c1;
c[i][j] = c2;
}
}
int ans = 0;
for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (c[i][j])
ans = max(ans, i * j);
cout << ans << endl;
return 0;
}