Submission #590403

#	Time	Username	Problem	Language	Result	Execution time	Memory
590403		dnialh	The Kingdom of JOIOI (JOI17_joioi)	Pypy 2	60 / 100	1041 ms	262144 KiB

joioi

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))

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40