import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); int N = Integer.parseInt(input[0]); int M = Integer.parseInt(input[1]); int[][] graphs = new int[N][M]; int[][] prefix = new int[N + 1][M + 1]; // 값 입력받기 for (int i = 0; i < N; ++i) { input = br.readLine().split(" "); for (int j = 0; j < M; ++j) { graphs[i][j] = Integer.parseInt(input[j]); } } prefix[1][1] = graphs[0][0]; // 누적합 2행 2열 초기화 for (int i = 2; i <= N; ++i) { prefix[i][1] = graphs[i - 1][0] + prefix[i - 1][1]; } for (int i = 2; i <= M; ++i) { prefix[1][i] = graphs[0][i - 1] + prefix[1][i - 1]; } // 누적합 for (int i = 2; i <= N; ++i) { for (int j = 2; j <= M; ++j) { prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + graphs[i - 1][j - 1]; } } int ans = 0; // 정답 값 // 일자로 길게 4칸일 경우 // 1. 가로 for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M - 3; ++j) { ans = Math.max(ans, prefix[i][j + 3] - prefix[i][j - 1] - prefix[i - 1][j + 3] + prefix[i - 1][j - 1]); } } // 2. 세로 for (int i = 1; i <= N - 3; ++i) { for (int j = 1; j <= M; ++j) { ans = Math.max(ans, prefix[i + 3][j] - prefix[i + 3][j - 1] - prefix[i - 1][j] + prefix[i - 1][j - 1]); } } // 2x2 정사각형 for (int i = 1; i < N; ++i) { for (int j = 1; j < M; ++j) { ans = Math.max(ans, prefix[i + 1][j + 1] - prefix[i - 1][j + 1] - prefix[i + 1][j - 1] + prefix[i - 1][j - 1]); } } // 6칸중 4칸 // 1. 세로 for (int i = 1; i < N - 2; ++i) { for (int j = 1; j < M - 1; ++j) { int sum = prefix[i + 2][j + 1] - prefix[i - 1][j + 1] - prefix[i + 2][j - 1] + prefix[i - 1][j - 1]; // ㄱㄴ 합친 모양 ans = Math.max(ans, sum - graphs[i - 1][j] - graphs[i + 1][j - 1]); ans = Math.max(ans, sum - graphs[i - 1][j - 1] - graphs[i + 1][j]); // ㅏ, ㅓ 모양 ans = Math.max(ans, sum - graphs[i - 1][j] - graphs[i + 1][j]); ans = Math.max(ans, sum - graphs[i - 1][j - 1] - graphs[i + 1][j - 1]); // L 모양 ans = Math.max(ans, sum - graphs[i - 1][j] - graphs[i][j]); ans = Math.max(ans, sum - graphs[i - 1][j - 1] - graphs[i][j - 1]); ans = Math.max(ans, sum - graphs[i][j] - graphs[i + 1][j]); ans = Math.max(ans, sum - graphs[i][j - 1] - graphs[i + 1][j - 1]); } } // 2. 가로 for (int i = 1; i < N - 1; ++i) { for (int j = 1; j < M - 2; ++j) { int sum = prefix[i + 1][j + 2] - prefix[i - 1][j + 2] - prefix[i + 1][j - 1] + prefix[i - 1][j - 1]; // ㄱㄴ 합친 모양 ans = Math.max(ans, sum - graphs[i - 1][j + 1] - graphs[i][j - 1]); ans = Math.max(ans, sum - graphs[i - 1][j - 1] - graphs[i][j + 1]); // ㅗ, ㅜ 모양 ans = Math.max(ans, sum - graphs[i - 1][j - 1] - graphs[i - 1][j + 1]); ans = Math.max(ans, sum - graphs[i][j - 1] - graphs[i][j + 1]); // L 모양 ans = Math.max(ans, sum - graphs[i - 1][j - 1] - graphs[i - 1][j]); ans = Math.max(ans, sum - graphs[i][j - 1] - graphs[i][j]); ans = Math.max(ans, sum - graphs[i - 1][j] - graphs[i - 1][j + 1]); ans = Math.max(ans, sum - graphs[i][j] - graphs[i][j + 1]); } } System.out.println(ans); } }

제출 #134581

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: