Codeforces 161E (263E) Rhombus

問題

nxm行列aijが与えられる。
関数x, yを
f(x, y) = Σ[i=1 to n]Σ[j=1 to m]a[i][j] * max(0, k - abs(i - x) - abs(j - y))
と定義する。

k≦x≦n - k + 1
k≦y≦m - k + 1
を満たし、f(x, y)を最小にするようなx, yの組を求めよ。
答えが複数ある場合どれを出力してもかまわない。

制約条件

n, m≦1000
2 * k≦min(n, m)

方針

累積和を使って、差分を効率的に計算する。
差分は、O(k)で求まればよい。（全体で500^3くらいの計算量になるので）

斜めの累積和を使うともっと計算量が落ちる。

ソースコード

const int MX = 1010;
int h, w, k;
int a[MX][MX];
ll s[MX][MX], ss[MX][MX];

inline ll calc(int y, int x, int Y, int X){
	Y++; X++;
	return s[Y][X] - s[Y][x] - s[y][X] + s[y][x];
}

int main(){
	scanf("%d%d%d", &h, &w, &k);
	ll sum = 0;
	rep(i, h) rep(j, w){
		scanf("%d", a[i] + j);
		s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + a[i][j];
		sum += (ll)a[i][j] * max(0, k - abs(i - k + 1) - abs(j - k + 1));
	}
	ss[k - 1][k - 1] = sum;
	ll mxs = sum;
	int my = k - 1, mx = k - 1;
	
	for(int i = k - 1; i <= h - k; i++) for(int j = k - 1; j <= w - k; j++){
		if(j == k - 1){
			if(i == k - 1) continue;
			ss[i][j] = ss[i - 1][j];
			rep(l, k){
				ss[i][j] -= calc(i - l - 1, j - k + l + 1, i - l - 1, j + k - l - 1);
				ss[i][j] += calc(i + l, j - k + l + 1, i + l, j + k - l - 1);
			}
		}
		else{
			ss[i][j] = ss[i][j - 1];
			rep(l, k){
				ss[i][j] -= calc(i - k + l + 1, j - l - 1, i + k - l - 1, j - l - 1);
				ss[i][j] += calc(i - k + l + 1, j + l, i + k - l - 1, j + l);
			}
		}
		if(ss[i][j] > mxs){
			mxs = ss[i][j];
			my = i; mx = j;
		}
	}
	cout << my + 1 << " " << mx + 1 << endl;
	
	return 0;
}