Submission #76454641

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1e18
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=505,M=2505;
const int mod=1e9+7;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,k;
int sum[N][N];
string s[N];
inline int calc(int a,int b,int c,int d){
	return (sum[b][d]-sum[b][c-1]-sum[a-1][d]+sum[a-1][c-1]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int tc=1;
	while(tc--){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)
        	cin>>s[i],s[i]=" "+s[i];
        for(int i=1;i<=n;i++)
        	for(int j=1;j<=m;j++)
        		sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]-'0');
        int ans=0;
        for(int i=1;i<=n;i++){
        	for(int j=i;j<=n;j++){
        		int pos=1,r=1;
        		for(int x=1;x<=m;x++){
        			if(pos<x) pos=x; 
        			while(calc(i,j,x,pos)<k && pos<=m) ++pos;
        			if(r<pos) r=pos;
        			while(calc(i,j,x,r)<=k && r<=m) ++r;
        			ans=ans+r-pos;
				}
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}
/*

*/

Submission Info

Judge Result