Submission #590390

#	Time	Username	Problem	Language	Result	Execution time	Memory
590390		dnialh	The Kingdom of JOIOI (JOI17_joioi)	Pypy 3	0 / 100	44 ms	18960 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)

def solve(b):
    lo = -1
    hi = tol

    pref_max = []
    suff_min = []
    
    for l in b:
        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)
            far = min(ind, far)

            ot = suff_min[i][w - far]
            if ot < tol - test:
                good = False
                break

        if good:
            hi = test
        else:
            lo = test

    return hi


out = []
for _ in range(4):
    out.append(solve(board))
    board = rot(board)

print(min(out))

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