cntSQ

#include<bits/stdc++.h>
using namespace std;
ifstream f("cntsq.in");
ofstream g("cntsq.out");
int n,m,dp[1002][1002][4],aib[1002],t[1002];
long long ans=0;
vector<int>q[1002];
char v[1002][1002];

void update (int x)
{
    for(int i=x;i<=1000;i+=(i&-i))
        ++aib[i];
}

int query(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=(i&-i))
        sum+=aib[i];
    return sum;
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
        f>>v[i][j];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(v[i][j]=='1')
                dp[i][j][0]=dp[i-1][j][0]+1,dp[i][j][1]=dp[i][j-1][1]+1,++ans;
    for(int i=n;i>=1;--i)
        for(int j=m;j>=1;--j)
            if(v[i][j]=='1')
                dp[i][j][2]=dp[i+1][j][2]+1,dp[i][j][3]=dp[i][j+1][3]+1;
    int nr=max(n,m);
    for(int j=1;j<=m;++j)
    {
        int i=1,jj=j;
        memset(aib,0,sizeof(aib));
        memset(t,0,sizeof(t));
        while(i<=n&&jj<=m)
        {
            if (v[i][jj]=='0')
            {
                ++i;++jj;
                continue;
            }
            t[i]=query(1000)-query(i-1);
            int aux=min(dp[i][jj][0],dp[i][jj][1]);
            int aux2=min(dp[i][jj][2],dp[i][jj][3]);
            q[i-aux].push_back(i);
            update(i+aux2-1);
            ++i,++jj;
        }
        memset(aib,0,sizeof(aib));
        i=1,jj=j;
        while(i<=n&&jj<=m)
        {
            int aux2=min(dp[i][jj][2],dp[i][jj][3]);
            if(v[i][jj]=='1')
                update(i+aux2-1);
            for(int k=0;k<(int)q[i].size();++k)
                t[q[i][k]]-=(query(1000)-query(q[i][k]-1));
            ++i;++jj;
        }
        for(int k=1;k<=nr;++k)
            ans+=t[k],q[k].clear();
    }
    for(int i=2;i<=n;++i)
    {
        int ii=i,j=1;
        memset(aib,0,sizeof(aib));
        memset(t,0,sizeof(t));
        while(ii<=n&&j<=m)
        {
            if(v[ii][j]=='0')
            {
                ++ii;++j;
                continue;
            }
            t[j]=query(1000)-query(j-1);
            int aux=min(dp[ii][j][0],dp[ii][j][1]);
            int aux2=min(dp[ii][j][2],dp[ii][j][3]);
            q[j-aux].push_back(j);
            update(j+aux2-1);
            ++ii,++j;
        }
        memset(aib,0,sizeof(aib));
        ii=i;j=1;
        while(ii<=n&&j<=m)
        {
            int aux2=min(dp[ii][j][2],dp[ii][j][3]);
            if(v[ii][j]=='1')
                update(j+aux2-1);
            for(int k=0;k<(int)q[j].size();++k)
                t[q[j][k]]-=(query(1000)-query(q[j][k]-1));
            ++ii;++j;
        }
        for(int k=1;k<=nr;++k)
            ans+=t[k],q[k].clear();
    }
    g<<ans;
    return 0;
}