import sys as sus
input = sus.stdin.readline
from bisect import bisect_right as bi
h, w = map(int, input().split())
def rot(b):
bb = b[::-1]
nb = []
for i in range(len(bb[0])):
curr = []
for l in bb:
curr.append(l[i])
nb.append(curr)
global w, h
w, h = h, w
return nb
board = [list(map(int, input().split())) for _ in range(h)]
smol = min(min(l) for l in board)
for l in board:
for i in range(w):
l[i] -= smol
tol = max(max(l) for l in board)
#
out = []
for _ in range(4):
lo = -1
hi = tol
pref_max = []
suff_min = []
for l in board:
pf = [0]
for v in l:
pf.append(max(pf[-1], v))
pref_max.append(pf)
suff = [1000000000]
for v in l[::-1]:
suff.append(min(suff[-1], v))
suff_min.append(suff)
while hi - lo > 1:
test = (lo + hi) // 2
far = w
good = True
for i in range(h):
ind = bi(pref_max[i], test) - 1
far = min(ind, far)
ot = suff_min[i][w - far]
#if test == 8:
# print(i, ind, far, ot)
if ot < tol - test:
good = False
break
if good:
hi = test
else:
lo = test
out.append(hi)
board = rot(board)
print(min(out))
Compilation message
Sorry: IndentationError: unexpected indent (joioi.py, line 1)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
20280 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
20280 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
20280 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
