oj.uz

Submission #590390

# Submission time Handle Problem Language Result Execution time Memory
590390 2022-07-05T22:08:57 Z dnialh The Kingdom of JOIOI (JOI17_joioi) PyPy 3
0 / 100
 44 ms 18960 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)

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.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18344 KB Output is correct
2 Correct 35 ms 18216 KB Output is correct
3 Correct 43 ms 18948 KB Output is correct
4 Correct 44 ms 18824 KB Output is correct
5 Correct 40 ms 18960 KB Output is correct
6 Incorrect 43 ms 18720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18344 KB Output is correct
2 Correct 35 ms 18216 KB Output is correct
3 Correct 43 ms 18948 KB Output is correct
4 Correct 44 ms 18824 KB Output is correct
5 Correct 40 ms 18960 KB Output is correct
6 Incorrect 43 ms 18720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18344 KB Output is correct
2 Correct 35 ms 18216 KB Output is correct
3 Correct 43 ms 18948 KB Output is correct
4 Correct 44 ms 18824 KB Output is correct
5 Correct 40 ms 18960 KB Output is correct
6 Incorrect 43 ms 18720 KB Output isn't correct
7 Halted 0 ms 0 KB -