第6回日本情報オリンピック 春合宿 1日目 問題3 「ショッピングモール」 (Mall)

二次元累積和やるだけです。

ある区間に何個-1があるかを二次元累積和で求められるようにし。
その区間の資源の合計も二次元累積和で求められるようにする。
DPでの解法もある（？）
計算量はO(n ^ 2).

累積和についてよくわからなかったら、

もし女子大生プログラマに『アルゴリズム』を図解で教えるとしたら - paiza開発日誌
を見てみてください。（「累積和」で検索して出てきただけだし読んでないけど...）

#include <bits/stdc++.h>

using namespace std;

int ch[1002][1002];
int d[1002][1002];
int m,n,a,b,ans=1000000000;
int main(){
	scanf("%d%d%d%d",&m,&n,&a,&b);

	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			scanf("%d",&d[i][j]);
			if(d[i][j] == -1)ch[i][j] = -1,d[i][j] = 0;
		}
	}
	for(int i = 2;i <= m;i++){
		d[1][i] += d[1][i-1];
		ch[1][i] += ch[1][i-1];
	}
	for(int i = 2;i <= n;i++){
		d[i][1] += d[i-1][1];
		ch[i][1] += ch[i-1][1];
	}
	for(int i = 2;i <= n;i++){
		for(int j = 2;j <= m;j++){
			d[i][j] += d[i-1][j] + d[i][j-1] -d[i-1][j-1];
			ch[i][j] += ch[i-1][j] + ch[i][j-1] - ch[i-1][j-1];
		}
	}
	for(int i = 1;i <= n - b;i++){
		for(int j = 1;j <= m - a;j++){
			if(ch[i+b-1][j+a-1] - ch[i-1][j+a-1] - ch[i+b-1][j-1] + ch[i-1][j-1] != 0)continue;
			ans = min(ans,d[i+b-1][j+a-1] - d[i-1][j+a-1] - d[i+b-1][j-1] + d[i-1][j-1]);
		}
	}
	printf("%d\n",ans);
	return 0;
}