Codeforces 131 F. Present to Mom

問題

nxmマスのグリッドにおいて、「星」とは

 1
111
 1

のような1の並びを言う。星は互いに一部が重なっていてもよい。

nxmマス長方形の部分長方形で、星をk個以上含むものはいくつあるか、求めよ。

制約条件

n,m≦500

方針

部分長方形の上下を適当に決め付ける。
その上で右方向にしゃくとりをして、k個以上星を含むような長方形をO(m)で求める。

しゃくとりをする際に、一列にいくつ星が含まれるかをO(1)で求める必要がある。
これは前処理であらかじめ累積和を計算しておくことでできる。

ソースコード

int n,m,k;
bool star[600][600];
int sum[600][600];
char in[600][600];

void run()
{
	cin>>n>>m>>k;
	rep(i,n)cin>>in[i];
	rep(i,n)rep(j,m){
		if(in[i][j]=='1'&&in[i+1][j]=='1'&&in[i+2][j]=='1'&&
			j&&in[i+1][j-1]=='1'&&in[i+1][j+1]=='1')star[i][j]=1;
	}
	ll ans=0;
	rep(i,n)rep(j,m)sum[i+1][j+1]=star[i][j]+sum[i][j+1]+sum[i+1][j]-sum[i][j];

	rep(a,n)for(int b=a+3;b<=n;b++){
		int l=0,r=2,cnt=0;
		for(;l<m;l++){
			while(r<=m&&cnt<k){
				r++;
				cnt+=sum[b-2][r-1]-sum[a][r-1]-(sum[b-2][r-2]-sum[a][r-2]);
			}
			if(cnt<k||r>m)break;
			ans+=m-r+1;
			cnt-=sum[b-2][l+2]-sum[a][l+2]-(sum[b-2][l+1]-sum[a][l+1]);
		}
	}
	cout<<ans<<endl;
}