Submission #1444885

---

Source Code Expand

import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    static int[][] memo;
    static int[][] D;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        D = new int[N][N];
        for (int i : IntStream.range(0, N).toArray()) {
            for (int j : IntStream.range(0, N).toArray()) {
                D[i][j] = scan.nextInt();
            }
        }

        memo = new int[N][N];
        for (int i : IntStream.range(0, N).toArray()) {
            for (int j : IntStream.range(0, N).toArray()) {
                int x = N - 1 - i;
                int y = N - 1 -j;
                if (x == N -1 && y == N - 1) {
                    memo[x][y] = D[x][y];
                } else if (x == N - 1) {
                    memo[x][y] = memo[x][y + 1] + D[x][y];
                } else if (y == N -1) {
                    memo[x][y] = memo[x + 1][y] + D[x][y];
                } else {
                    memo[x][y] = memo[x][y + 1] + memo[x + 1][y] - memo[x + 1][y + 1] + D[x][y];
                }
            }
        }

        int NN = N * N;
        int[] score = new int[NN+1];
        for (int i : IntStream.range(1, NN).toArray()) {
            for (int j : IntStream.range(1, NN).toArray()) {
                int S = i * j;
                if (S > NN) {
                    break;
                }
            score[S] = Math.max(score[S], max(i, j, N));
            }
        }

        int tmpScore = 0;
        for (int i :IntStream.range(0, NN + 1).toArray()){
            if (tmpScore > score[i]) {
                score[i] = tmpScore;
            } else {
                tmpScore = score[i];
            }
        }

        int Q = scan.nextInt();
        for (int i :IntStream.range(0, Q).toArray()){
            int p = scan.nextInt();
            System.out.println(score[p]);
        }
    }

    static int max(int x, int y, int N) {
        if (x > N || y > N) {
            return 0;
        }
        int max = 0;
        for (int i : IntStream.range(0, N - x + 1).toArray()) {
            for (int j : IntStream.range(0, N - y + 1).toArray()) {
                if (i + x == N && j + y == N) {
                    max = Math.max(max, memo[i][j]);
                } else if (i + x == N) {
                    max = Math.max(max, memo[i][j] - memo[i][j + y]);
                } else if(j + y == N) {
                    max = Math.max(max, memo[i][j] - memo[i + x][j]);
                } else {
                    max = Math.max(max, memo[i][j] - memo[i][j + y] - memo[i + x][j] + memo[i + x][ j +y]);
                }
            }
        }
        return max;
    }
}

Submission Info

Judge Result