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; }