-
Notifications
You must be signed in to change notification settings - Fork 0
/
1451.py
57 lines (49 loc) · 1.66 KB
/
1451.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# 직사각형으로 나누기
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
p_square = [[0 for _ in range(M + 1)]]
for _ in range(N):
row = input().rstrip()
p_row = [0]
for i in range(1, M + 1):
p_row.append(
int(row[i - 1]) + p_square[-1][i] + p_row[-1] - p_square[-1][i - 1]
)
p_square.append(p_row)
max_s = 0
for i in range(1, N + 1):
for j in range(1, M + 1):
if i == N and j == M:
continue
elif i == N:
for k in range(j + 1, M):
s1 = p_square[N][j]
s2 = p_square[N][k] - s1
s3 = p_square[N][M] - s1 - s2
max_s = max(s1 * s2 * s3, max_s)
for k in range(1, N):
s1 = p_square[N][j]
s2 = p_square[k][M] - p_square[k][j]
s3 = p_square[N][M] - s1 - s2
max_s = max(s1 * s2 * s3, max_s)
elif j == M:
for k in range(i + 1, N):
s1 = p_square[i][M]
s2 = p_square[k][M] - s1
s3 = p_square[N][M] - s1 - s2
max_s = max(s1 * s2 * s3, max_s)
for k in range(1, M):
s1 = p_square[i][M]
s2 = p_square[N][k] - p_square[i][k]
s3 = p_square[N][M] - s1 - s2
max_s = max(s1 * s2 * s3, max_s)
else:
s1 = p_square[i][j]
s2 = p_square[i][M] - s1
s3 = p_square[N][M] - s1 - s2
max_s = max(s1 * s2 * s3, max_s)
s2 = p_square[N][j] - s1
s3 = p_square[N][M] - s1 - s2
max_s = max(s1 * s2 * s3, max_s)
print(max_s)