C++14(g++5.4) 解法, 执行用时: 151ms, 内存消耗: 39640K, 提交时间: 2019-08-11 13:44:27

#include<bits/stdc++.h>
#define maxn 3005
#define LL long long
using namespace std;
int n, m, a[maxn][maxn], ans, s[maxn], pre[maxn], q[maxn], tp;
char c[maxn];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", c + 1);
		for (int j = 1; j <= m; j++) a[i][j] = c[j] - '0';
	}
	for (int i = 1; i <= n; i++) {
		tp = 0;
		for (int j = 1; j <= m + 1; j++) {
			s[j] = (a[i][j] ? s[j] + 1 : 0), pre[j] = pre[j - 1] + a[i + 1][j];
			while (s[q[tp]] > s[j]) ans += (pre[j - 1] - pre[q[tp - 1]] < j - 1 - q[tp - 1] && s[q[tp - 1]] < s[q[tp]]), tp--;
			q[++tp] = j;
		}
	}
	printf("%d", ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 129ms, 内存消耗: 39648K, 提交时间: 2019-08-10 22:44:59

#include<bits/stdc++.h>
#define maxn 3005
#define LL long long
using namespace std;
int n,m,a[maxn][maxn],ans,s[maxn],pre[maxn],q[maxn],tp;
char c[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        for(int j=1;j<=m;j++) a[i][j]=c[j]-'0';
    }
    for(int i=1;i<=n;i++){
        tp=0;
        for(int j=1;j<=m+1;j++){
            s[j]=(a[i][j]?s[j]+1:0),pre[j]=pre[j-1]+a[i+1][j];
            while(s[q[tp]]>s[j]) ans+=(pre[j-1]-pre[q[tp-1]]<j-1-q[tp-1]&&s[q[tp-1]]<s[q[tp]]),tp--;
            q[++tp]=j;
        }
    }
    printf("%d",ans);
}