CREC01 - Đếm hình chữ nhật trên bảng 0-1
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
using namespace std;
const int N = 1010;
char a[N];
int c[N][N];
int h[N];
int s[N];
int size;
int n, m;
int main() {
cin >> m >> n;
for (int i = 1; i <= m; ++i) {
cin >> (a + 1);
for (int j = 1; j <= n; ++j) h[j] = a[j] == '1' ? h[j] + 1 : 0;
size = 0;
for (int j = 0; j <= n + 1; ++j) {
while (size && h[s[size]] >= h[j]) {
int w = j - 1 - s[size - 1];
++c[max(h[s[size - 1]], h[j]) + 1][w];
--c[h[s[size]] + 1][w];
--size;
}
s[++size] = j;
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) c[i + 1][j] += c[i][j];
int cur = 0;
for (int j = n; j >= 1; --j) {
cur += c[i][j];
c[i][j] = c[i][j + 1] + cur;
}
}
long long ans = 0;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
ans += c[i][j];
cout << ans << endl;
}