CREC01 - Đếm hình chữ nhật trên bảng 0-1
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<stack>
#define MAX 1010
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
char a[MAX][MAX];
int h[MAX][MAX];
int l[MAX];
int c[MAX][MAX];
int m,n;
stack<int> st;
void init(void) {
scanf("%d",&m);
scanf("%d",&n);
FOR(i,1,m) {
scanf("%s",a[i]+1);
FOR(j,1,n) {
if (a[i][j]=='1') h[i][j]=h[i-1][j]+1;
else h[i][j]=0;
}
}
}
void count(void) {
FOR(i,1,m) {
while (!st.empty()) st.pop();
l[1]=1;
c[i][1]=h[i][1];
FOR(j,2,n) {
if (h[i][j]>h[i][j-1]) {
l[j]=j;
st.push(j-1);
}
else {
while (!st.empty() && h[i][st.top()]>=h[i][j]) st.pop();
if (st.empty()) l[j]=1;
else l[j]=st.top()+1;
}
c[i][j]=c[i][l[j]-1]+h[i][j]*(j-l[j]+1);
}
}
long long res=0;
FOR(i,1,m) FOR(j,1,n) res+=c[i][j];
printf("%lld",res);
}
int main(void) {
init();
count();
return 0;
}