Submission #590407

#TimeUsernameProblemLanguageResultExecution timeMemory
590407dnialhThe Kingdom of JOIOI (JOI17_joioi)Pypy 3
60 / 100
1154 ms262144 KiB
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 i in range(h): pf = [0] for j in range(w): if _ == 0: v = board[i][j] elif _ == 1: v = board[~i][j] elif _ == 2: v = board[~i][~j] else: v = board[i][~j] pf.append(max(pf[-1], v)) pref_max.append(pf) suff = [1000000000] for j in range(w - 1, -1, -1): if _ == 0: v = board[i][j] elif _ == 1: v = board[~i][j] elif _ == 2: v = board[~i][~j] else: v = board[i][~j] 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) #w, h = h, w print(min(out))
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...