시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 671 172 131 29.841%

문제

세준이는 N*M크기로 직사각형에 수를 N*M개 써놓았다.

세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.

어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.

출력

세 개의 작은 직사각형의 합의 곱의 최대값을 출력한다.

예제 입력

1 8
11911103

예제 출력

108

예제 입력 2

3 3
123
456
789

예제 출력 2

3264

예제 입력 3

3 1
7
9
3

예제 출력 3

189

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: jsa3824