#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2500 + 4;
int pre[N][N];
int r[N][N];
int d[N][N];
int get(int i, int j, int ii, int jj) {return pre[ii+1][jj+1] - pre[ii+1][j] - pre[i][jj+1] + pre[i][j];}
long long count_rectangles(std::vector<std::vector<int>> a) {
memset(r, -1, sizeof r);
memset(d, -1, sizeof d);
int n = a.size();
int m = a[0].size();
for (int i=0; i<n; i++) for (int j=0; j<m; j++) pre[i+1][j+1] = a[i][j] + pre[i+1][j] + pre[i][j+1] - pre[i][j];
for (int i=1; i+1<n; i++) for (int j=m-2; j>=1; j--) if (!a[i][j]) {
if (j==m-2 || a[i][j+1]==1) r[i][j]=j;
else r[i][j] = r[i][j+1];
}
for (int j=1; j+1<m; j++) for (int i=n-2; i>=1; i--) if (!a[i][j]) {
if (i==n-2 || a[i+1][j]==1) d[i][j]=i;
else d[i][j] = d[i+1][j];
}
int ans=0;
for (int i=1; i+1<n; i++) for (int j=1; j+1<m; j++) if (!a[i][j]) {
int ii=r[i][j];
int jj=d[i][j];
ans += get(i,j,ii,jj)==0 && get(i-1,j,i-1,jj)==jj-j+1 && get(ii+1,j,ii+1,jj)==jj-j+1 && get(i,j-1,ii,j-1)==ii-i+1 && get(i,jj+1,ii,jj+1)==ii-i+1;
}
return ans;
}
