oj.uz

답안 #636115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636115 2022-08-28T07:42:36 Z Bruteforceman The Kingdom of JOIOI (JOI17_joioi) PyPy 3
0 / 100
 71 ms 20280 KB 
    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)

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 71 ms 20280 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 71 ms 20280 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 71 ms 20280 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -