AtCoder Beginner Contest #005 D: おいしいたこ焼きの焼き方 （2次元の累積和）

問題

D: おいしいたこ焼きの焼き方 - AtCoder Beginner Contest #005 | AtCoder

解法

たこ焼き器について、二次元の累積和を求めておく。クエリに対して作れる長方形を全列挙し、その長方形を(x,y)だけ平行移動した時に、長方形内部の美味しさの合計を計算する。

コード

import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] tMap = new int[N + 1][N + 1];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				tMap[i + 1][j + 1] = sc.nextInt();
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				tMap[i + 1][j + 1] += tMap[i + 1][j] + tMap[i][j + 1] - tMap[i][j];
			}
		}

		int Q = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int q = 0; q < Q; q++) {
			int query = sc.nextInt();
			int max = 0;
			for (int h = 1; h <= N; h++) {
				// h*wの長方形を考える
				int w = query / h;
				w = Math.min(w, N);
				if (w == 0) {
					break;
				}

				// h*wの長方形をx,yだけ平行移動させた時の長方形内の美味しさの合計を計算する
				for (int x = 0; h + x <= N; x++) {
					for (int y = 0; w + y <= N; y++) {
						int deli = tMap[h + x][w + y] - tMap[x][w + y] - tMap[h + x][y] + tMap[x][y];
						max = Math.max(deli, max);
					}
				}
			}

			sb.append(max + "\n");
		}
		sc.close();
		System.out.print(sb.toString());

	}

}