JOI 春合宿 2007 Day1 Mall

解法

2次元累積和を用いる．人が住んでいる場所は10^8以上の数字にすればよい．

実装(C++)

#include <cstdio>
using namespace std;
typedef long long lli;
const lli INF=1000000001;
lli MAP[1000][1000],SUM[1001][1001],_SUM[1001][1001];
int W,H;
int a,b;
int main() {
	scanf("%d%d%d%d",&W,&H,&a,&b);
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			scanf("%I64d",&MAP[j][i]);
			if(MAP[j][i]<0)MAP[j][i]=INF;
		}
	}
	for(int i=0;i<W;i++)
		for(int j=0;j<H;j++)
			_SUM[i][j+1]=_SUM[i][j]+MAP[i][j];

	for(int x=0;x<W;x++)
		for(int y=0;y<=H;y++)
			SUM[x+1][y]=SUM[x][y]+_SUM[x][y];

	lli ans=INF*30;
	for(int x=0;x<W;x++)
		for(int y=0;y<H;y++)
			if(x+a<=W&&y+b<=H)
				ans=min(ans,SUM[x+a][y+b]-SUM[x+a][y]-SUM[x][y+b]+SUM[x][y]);


	printf("%d\n",(int)ans);
}