Submission #4907150

---

Source Code Expand

#include<iostream>
#include<algorithm>
using namespace std;
long H,W;
int N,M;
string s[1000];
int sum[1001][1001];
int a[2002][2002];
main()
{
	cin>>H>>W>>N>>M;
	for(int i=0;i<N;i++)
	{
		cin>>s[i];
		for(int j=0;j<M;j++)sum[i+1][j+1]=s[i][j]=='#';
	}
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<=M;j++)
		{
			sum[i][j]+=(j>0?sum[i][j-1]:0)+(i>0?sum[i-1][j]:0)-(i>0&&j>0?sum[i-1][j-1]:0);
		}
	}
	if(sum[N][M]==0)
	{
		cout<<0<<endl;
		return 0;
	}
	if(H<2*N&&W<2*M)
	{
		long cnt=0;
		for(int i=0;i<H;i++)
		{
			for(int j=0;j<W;j++)
			{
				int x1=max(i-(H-N),0L),y1=max(j-(W-M),0L),x2=min(i+1,N),y2=min(j+1,M);
				cnt+=a[i][j]=sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1]>0;
			}
		}
		cout<<cnt<<endl;
	}
	else
	{
		long cnt=2*N*2*M;
		for(int i=0;i<2*N;i++)
		{
			for(int j=0;j<2*M;j++)
			{
				int x1=max(i-N,0),y1=max(j-M,0),x2=min(i+1,N),y2=min(j+1,M);
				cnt-=a[i][j]=sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1]>0;
			}
		}
		int id=0;
		while(sum[id+1][M]==0)id++;
		cnt+=(W-2*M)*id;
		id=N;
		while(sum[N][M]-sum[id-1][M]==0)id--;
		cnt+=(W-2*M)*(N-id);
		id=0;
		while(sum[N][id+1]==0)id++;
		cnt+=(H-2*N)*id;
		id=M;
		while(sum[N][M]-sum[N][id-1]==0)id--;
		cnt+=(H-2*N)*(M-id);
		cout<<H*W-cnt<<endl;
	}
}

Submission Info

Judge Result