Submission #147650

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

import java.util.*;
import java.util.Map.Entry;

public class Main {
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		final int n = sc.nextInt();
		int[][] map = new int[n][n];
		for(int i = 0;  i < n; i++){
			for(int j = 0; j < n; j++){
				map[i][j] = sc.nextInt();
			}
		}
		
		
		for(int i = 0;  i < n; i++){
			for(int j = 1; j < n; j++){
				map[i][j] += map[i][j-1];
			}
		}
		for(int i = 1;  i < n; i++){
			for(int j = 0; j < n; j++){
				map[i][j] += map[i-1][j];
			}
		}
		
		final int area = n * n + 1;
		int[] ans = new int[area];
		Arrays.fill(ans, 0);
		
		for(int height = 1; height <= n; height++){
			for(int width = 1; width <= n; width++){
				final int size = height * width;
				final int max_y = n - (height - 1);
				final int max_x = n - (width - 1);
				
				for(int start_y = 0; start_y < max_y; start_y++){
					for(int start_x = 0; start_x < max_x; start_x++){
						final int end_y = start_y + height - 1;
						final int end_x = start_x + width - 1;
						
						
						
						//System.out.println(start_x + " " + start_y + " " + end_x + " " + end_y + " " + max_x + " " + max_y);
						
						
						int value = map[end_y][end_x];
						if(start_x > 0){
							value -= map[end_y][start_x - 1];
						}
						if(start_y > 0){
							value -= map[start_y - 1][end_x];
						}
						if(start_x > 0 && start_y > 0){
							value += map[start_y - 1][start_x - 1];
						}
						
						//System.out.println(value);
						
						ans[size] = Math.max(ans[size], value);
					}
				}
				
			}
		}
		
		int max = 0;
		for(int i = 0; i < area; i++){
			max = Math.max(max, ans[i]);
			ans[i] = max;
		}
		
		final int q = sc.nextInt();
		for(int tt = 0; tt < q; tt++){
			final int p = sc.nextInt();
		
			System.out.println(ans[p]);
		}
		
	}
	
	public static class Scanner {
		
		private BufferedReader br;
		private StringTokenizer tok;
		
		public Scanner(InputStream is) throws IOException{
			br = new BufferedReader(new InputStreamReader(is));
			getLine();
		}
		
		private void getLine() throws IOException{
			while(tok == null || !tok.hasMoreTokens()){
				tok = new StringTokenizer(br.readLine());
			}
		}
		
		private boolean hasNext(){
			return tok.hasMoreTokens();
		}
		
		public String next() throws IOException{
			if(hasNext()){
				return tok.nextToken();
			}else{
				getLine();
				return tok.nextToken();
			}
		}
		
		public int nextInt() throws IOException{
			if(hasNext()){
				return Integer.parseInt(tok.nextToken());
			}else{
				getLine();
				return Integer.parseInt(tok.nextToken());
			}
		}
		
		public long nextLong() throws IOException{
			if(hasNext()){
				return Long.parseLong(tok.nextToken());
			}else{
				getLine();
				return Long.parseLong(tok.nextToken());
			}
		}
		
		public double nextDouble() throws IOException{
			if(hasNext()){
				return Double.parseDouble(tok.nextToken());
			}else{
				getLine();
				return Double.parseDouble(tok.nextToken());
			}
		}
		
		public void close() throws IOException{
			br.close();
		}
	}
}

Submission Info

Judge Result