csa_cntgigelmat.cpp

int d[2010][2010], u[2010][2010], l[2010][2010], r[2010][2010], dig[2010][2010];
int main() {  
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  
  int n, m; cin >> n >> m;
  vector<vector<int>> v(n, vector<int>(m));
  REP(i,n) {
    string s; cin >> s;
    REP(j,m) v[i][j] = s[j]-'0';
  }
  REP(i,n) {
    REP(j,m) {
      if(v[i][j] == 0) {
        l[i][j] = 0;
        u[i][j] = 0;
        dig[i][j] = 0;
      }else{
        l[i][j] = (j-1>=0?l[i][j-1]:0) + 1;
        u[i][j] = (i-1>=0?u[i-1][j]:0) + 1;
        dig[i][j] = (i-1>=0&&j-1>=0?dig[i-1][j-1]:0) + 1;
      }
    }
  }
  for(int i=n-1; i>=0; i--) {
    for(int j=m-1; j>=0; j--) {
      if(v[i][j] == 0) {
        r[i][j] = 0;
        d[i][j] = 0;
      }else{
        r[i][j] = (j+1<m?r[i][j+1]:0) + 1;
        d[i][j] = (i+1<n?d[i+1][j]:0) + 1;
      }
    }
  }
  ll ans = 0;
  for(int i=-n; i<=m; i++) {
    vector<tuple<int, int, int>> query;
    for(int y=0; y<n; y++) {
      int x = i+y;
      if(x >= 0 && x < m) {
        int c = min(r[y][x], d[y][x]);
        query.push_back({x, 1, y});
        query.push_back({x+c, 2, y});
      }
    }
    sort(all(query));
    BIT<int> bit(n+m);
    for(auto[x, type, y]: query) {
      if(type == 1) {
        bit.add(y+1, 1);
        int c = min({dig[y][x], l[y][x], u[y][x]});
        ans += bit.rangesum(y-c+2, y+1);
      }else{
        bit.add(y+1, -1);
      }
    }
  }
  cout << ans << endl;
  return 0;
}