Codeforces 173 C. Spiral Maximum

問題

n x mのグリッドに数字が書かれている。
グリッドの数字を渦のように足す(図参照)


このとき、全ての足し方のうち、和が最大になるような足し方の和を求めよ。

制約条件

n, m≦500

方針

全部の渦を試す。
ナイーブにやると、O(n^2m^2)かかるので、工夫が必要。


一つ大きいサイズの渦は、正方形から、現在の渦を引くと、残りの部分がそのまま渦になっている。
なので、渦を大きくするのは、正方形の部分の和を累積和を使って求めることで、O(1)でできる。

ソースコード

int h, w, a[500][500], s[501][501];
void run()
{
	cin >> h >> w;
	rep(i, h) rep(j, w){
		cin >> a[i][j];
		s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + a[i][j];
	}
	
	int ans = -1e9;
	rep(i, h) rep(j, w){
		int tmp = a[i][j];
		for(int d = 1; d <= min(i, j) && d <= min(h-i-1, w-j-1); d++){
			int sum = s[i+d+1][j+d+1] - s[i-d][j+d+1] - s[i+d+1][j-d] + s[i-d][j-d];
			sum -= tmp + a[i - d + 1][j - d];
			ans = max(ans, sum);
			tmp = sum;
		}
	}
	cout << ans << endl;
}