//숏코드 : https://www.acmicpc.net/source/40685070
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main{
static int[][] map;
static long[][] sum;
static long max;
static long w1;
static long w2;
static long w3;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
map = new int[N + 1][M + 1]; //직사각형 각각의 자연수 저장
sum = new long[N + 1][M + 1]; //해당 index까지의 합 저장
for (int i = 1; i <= N; i++) {
String[] stArray = br.readLine().split("");
for (int j = 1; j <= M; j++) {
map[i][j] = Integer.parseInt(stArray[j-1]);
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + map[i][j];
}
}
//1번 방법
max = Integer.MIN_VALUE;
for (int y = 1; y <= N - 2; y++) {
for (int y2 = y + 1; y2 <= N - 1; y2++) {
w1 = sum(1, 1, M, y);
w2 = sum(1, y + 1, M, y2);
w3 = sum(1, y2 + 1, M, N);
getMax();
}
}
//2번 방법
for (int x = 1; x <= M - 2; x++) {
for (int x2 = x + 1; x2 <= M - 1; x2++) {
w1 = sum(1, 1, x, N);
w2 = sum(x + 1, 1, x2, N);
w3 = sum(x2+1, 1, M, N);
getMax();
}
}
//3번 방법
for (int x = 1; x <= M - 1; x++) {
for (int y = 1; y <= N - 1; y++) {
w1 = sum(1, 1, x, N);
w2 = sum(x + 1, 1, M, y);
w3 = sum(x + 1, y + 1, M, N);
getMax();
}
}
//4번 방법
for (int x = 1; x <= M - 1; x++) {
for (int y = 1; y <= N - 1; y++) {
w1 = sum(1, 1, x, y);
w2 = sum(1, y + 1, x, N);
w3 = sum(x + 1, 1, M, N);
getMax();
}
}
//5번 방법
for (int y = 1; y <= N - 1; y++) {
for (int x = 1; x <= M - 1; x++) {
w1 = sum(1, 1, M, y);
w2 = sum(1, y + 1, x, N);
w3 = sum(x + 1, y + 1, M, N);
getMax();
}
}
//6번 방법
for (int x = 1; x <= M - 1; x++) {
for (int y = 1; y <= N - 1; y++) {
w1 = sum(1, 1, x, y);
w2 = sum(x + 1, 1, M, y);
w3 = sum(1, y + 1, M, N);
getMax();
}
}
bw.write(String.valueOf(max));
bw.flush();
bw.close();
}
static private long sum(int x1, int y1, int x2, int y2) {
return sum[y2][x2] - sum[y2][x1 - 1] - sum[y1 - 1][x2] + sum[y1 - 1][x1 - 1];
}
static void getMax() {
if (max < w1 * w2 * w3) {
max = w1 * w2 * w3;
}
}
}직사각형으로 나누기 : https://www.acmicpc.net/problem/1451
반례집 : https://www.acmicpc.net/board/view/60463
직사각형으로 나누는 6가지 방법을 사용한다.
*표시 된 부분까지 포함하는 가상의 선을 그어보면 나오는 경우의 수가 총 6가지이다.
(1,1*) (1,2*) (1,3)
(2,1*) (2,2*) (2,3)
(3,1) (3,2) (3,3)
실제 문제를 해결할 때 이런 부분을 잘 정리할 수 있어야 할텐데..
연습을 통한 경험치를 쌓는게 답이 아닌가싶다.
(지식과 경험이 없는 상태에서 고민 해봤자 올바른 답이 나올 수 없는것 같다
어찌저찌 풀어도 결국 반례 앞에서 벽을 느낌)
각 case별로 그림을 그려놓고 차분히 생각하면 쉽게 구현이 가능하다.
감사하게도 위의 반례집을 이용하여 case1에서의 버그를 찾아냈다.
(두번째 sum의 y인덱스의 출발점을 1이 아닌 i로 오기했음.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
//반례집 :https://www.acmicpc.net/problem/1451
static long[][] map;
static boolean DBG = false;
static int N, M;
static long answer = Integer.MIN_VALUE;
static long sum(int sx, int sy, int ex, int ey) {
long sum = 0;
for (int i = sx; i <= ex; i++) {
for (int j = sy; j <= ey; j++) {
sum += map[i][j];
}
}
return sum;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new long[N + 1][M + 1];
for (int i = 1; i <= N; ++i) {
String s = br.readLine();
for (int j = 1; j <= M; ++j) {
map[i][j] = s.charAt(j - 1) - '0';
}
}
if (DBG) {
System.out.println("#INFO ");
System.out.printf("N : %d M : %d\n", N, M);
}
if (DBG)
System.out.println("#case1 가로 막대 3개");
for (int i = 1; i < N - 1; ++i) {
for (int j = i + 1; j < N; ++j) {
if (DBG) {
System.out.printf("[%d %d]", i, j);
System.out.printf("%d %d %d [%d]\n", sum(1, 1, i, M), sum(i + 1, 1, j, M), sum(j + 1, 1, N, M), sum(1, 1, i, M) * sum(i + 1, i, j, M) * sum(j + 1, 1, N, M));
}
answer = Math.max(answer, sum(1, 1, i, M) * sum(i + 1, 1, j, M) * sum(j + 1, 1, N, M));
}
}
if (DBG)
System.out.println("#case2 세로 막대 3개");
for (int i = 1; i < M - 1; ++i) {
for (int j = i + 1; j < M; ++j) {
if (DBG)
System.out.printf("%d %d %d\n", sum(1, 1, N, i), sum(1, i + 1, N, j), sum(1, j + 1, N, M));
answer = Math.max(answer, sum(1, 1, N, i) * sum(1, i + 1, N, j) * sum(1, j + 1, N, M));
}
}
if (DBG)
System.out.println("#case3 가로 막대 1개 + 세로 막대 2개");
for (int i = 1; i < N; ++i) {
for (int j = 1; j < M; ++j) {
if (DBG) {
System.out.printf("[%d %d]", i, j);
System.out.printf("%d %d %d\n", sum(1, 1, i, M), sum(i + 1, 1, N, j), sum(i + 1, j + 1, N, M));
}
answer = Math.max(answer, sum(1, 1, i, M) * sum(i + 1, 1, N, j) * sum(i + 1, j + 1, N, M));
}
}
if (DBG)
System.out.println("#case4 세로막대 1개 + 가로막대 2개");
for (int i = 1; i < N; ++i) {
for (int j = 1; j < M; ++j) {
if (DBG) {
System.out.printf("[%d %d]", i, j);
System.out.printf("%d %d %d\n", sum(1, 1, N, j), sum(1, j + 1, i, M), sum(i + 1, j + 1, N, M));
}
answer = Math.max(answer, sum(1, 1, N, j) * sum(1, j + 1, i, M) * sum(i + 1, j + 1, N, M));
}
}
if (DBG)
System.out.println("#case5 세로막대 2개 + 가로막대 1개");
for (int i = 1; i < N; ++i) {
for (int j = 1; j < M; ++j) {
if (DBG) {
System.out.printf("[%d %d]", i, j);
System.out.printf("%d %d %d\n", sum(1, 1, i, j), sum(1, j + 1, i, M), sum(i + 1, 1, N, M));
}
answer = Math.max(answer, sum(1, 1, i, j) * sum(1, j + 1, i, M) * sum(i + 1, 1, N, M));
}
}
if (DBG)
System.out.println("#case6 가로막대 2개 + 세로막대 1개");
for (int i = 1; i < N; ++i) {
for (int j = 1; j < M; ++j) {
if (DBG) {
System.out.printf("[%d %d]", i, j);
System.out.printf("%d %d %d\n", sum(1, 1, i, j), sum(i + 1, 1, N, j), sum(1, j + 1, N, M));
}
answer = Math.max(answer, sum(1, 1, i, j) * sum(i + 1, 1, N, j) * sum(1, j + 1, N, M));
}
}
System.out.println(answer);
}
}
