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;
}

Download