oj.uz

Submission #590403

# Submission time Handle Problem Language Result Execution time Memory
590403 2022-07-05T22:17:29 Z dnialh The Kingdom of JOIOI (JOI17_joioi) PyPy
60 / 100
 1041 ms 262144 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))

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19252 KB Output is correct
2 Correct 25 ms 19256 KB Output is correct
3 Correct 31 ms 20392 KB Output is correct
4 Correct 33 ms 20300 KB Output is correct
5 Correct 33 ms 20136 KB Output is correct
6 Correct 38 ms 20208 KB Output is correct
7 Correct 31 ms 20100 KB Output is correct
8 Correct 30 ms 20144 KB Output is correct
9 Correct 30 ms 20088 KB Output is correct
10 Correct 31 ms 20216 KB Output is correct
11 Correct 30 ms 20160 KB Output is correct
12 Correct 29 ms 20196 KB Output is correct
13 Correct 35 ms 20188 KB Output is correct
14 Correct 33 ms 20188 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19252 KB Output is correct
2 Correct 25 ms 19256 KB Output is correct
3 Correct 31 ms 20392 KB Output is correct
4 Correct 33 ms 20300 KB Output is correct
5 Correct 33 ms 20136 KB Output is correct
6 Correct 38 ms 20208 KB Output is correct
7 Correct 31 ms 20100 KB Output is correct
8 Correct 30 ms 20144 KB Output is correct
9 Correct 30 ms 20088 KB Output is correct
10 Correct 31 ms 20216 KB Output is correct
11 Correct 30 ms 20160 KB Output is correct
12 Correct 29 ms 20196 KB Output is correct
13 Correct 35 ms 20188 KB Output is correct
14 Correct 33 ms 20188 KB Output is correct
15 Correct 50 ms 21956 KB Output is correct
16 Correct 77 ms 26504 KB Output is correct
17 Correct 78 ms 26616 KB Output is correct
18 Correct 90 ms 27496 KB Output is correct
19 Correct 97 ms 27520 KB Output is correct
20 Correct 102 ms 27544 KB Output is correct
21 Correct 96 ms 27064 KB Output is correct
22 Correct 98 ms 27444 KB Output is correct
23 Correct 103 ms 27180 KB Output is correct
24 Correct 93 ms 27532 KB Output is correct
25 Correct 109 ms 27256 KB Output is correct
26 Correct 100 ms 27412 KB Output is correct
27 Correct 91 ms 27452 KB Output is correct
28 Correct 98 ms 27656 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19252 KB Output is correct
2 Correct 25 ms 19256 KB Output is correct
3 Correct 31 ms 20392 KB Output is correct
4 Correct 33 ms 20300 KB Output is correct
5 Correct 33 ms 20136 KB Output is correct
6 Correct 38 ms 20208 KB Output is correct
7 Correct 31 ms 20100 KB Output is correct
8 Correct 30 ms 20144 KB Output is correct
9 Correct 30 ms 20088 KB Output is correct
10 Correct 31 ms 20216 KB Output is correct
11 Correct 30 ms 20160 KB Output is correct
12 Correct 29 ms 20196 KB Output is correct
13 Correct 35 ms 20188 KB Output is correct
14 Correct 33 ms 20188 KB Output is correct
15 Correct 50 ms 21956 KB Output is correct
16 Correct 77 ms 26504 KB Output is correct
17 Correct 78 ms 26616 KB Output is correct
18 Correct 90 ms 27496 KB Output is correct
19 Correct 97 ms 27520 KB Output is correct
20 Correct 102 ms 27544 KB Output is correct
21 Correct 96 ms 27064 KB Output is correct
22 Correct 98 ms 27444 KB Output is correct
23 Correct 103 ms 27180 KB Output is correct
24 Correct 93 ms 27532 KB Output is correct
25 Correct 109 ms 27256 KB Output is correct
26 Correct 100 ms 27412 KB Output is correct
27 Correct 91 ms 27452 KB Output is correct
28 Correct 98 ms 27656 KB Output is correct
29 Correct 990 ms 262144 KB Output is correct
30 Correct 1041 ms 253076 KB Output is correct
31 Runtime error 927 ms 262144 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -