답안 #590401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590401	2022-07-05T22:16:36 Z	dnialh	The Kingdom of JOIOI (JOI17_joioi)	PyPy 3	60 / 100	901 ms	262144 KB

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

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	18220 KB	Output is correct
2	Correct	38 ms	18220 KB	Output is correct
3	Correct	45 ms	19056 KB	Output is correct
4	Correct	47 ms	18860 KB	Output is correct
5	Correct	47 ms	18796 KB	Output is correct
6	Correct	43 ms	18760 KB	Output is correct
7	Correct	59 ms	18920 KB	Output is correct
8	Correct	43 ms	18756 KB	Output is correct
9	Correct	47 ms	18984 KB	Output is correct
10	Correct	44 ms	18760 KB	Output is correct
11	Correct	46 ms	18808 KB	Output is correct
12	Correct	66 ms	18816 KB	Output is correct
13	Correct	43 ms	18988 KB	Output is correct
14	Correct	44 ms	18784 KB	Output is correct

Subtask #2

45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	18220 KB	Output is correct
2	Correct	38 ms	18220 KB	Output is correct
3	Correct	45 ms	19056 KB	Output is correct
4	Correct	47 ms	18860 KB	Output is correct
5	Correct	47 ms	18796 KB	Output is correct
6	Correct	43 ms	18760 KB	Output is correct
7	Correct	59 ms	18920 KB	Output is correct
8	Correct	43 ms	18756 KB	Output is correct
9	Correct	47 ms	18984 KB	Output is correct
10	Correct	44 ms	18760 KB	Output is correct
11	Correct	46 ms	18808 KB	Output is correct
12	Correct	66 ms	18816 KB	Output is correct
13	Correct	43 ms	18988 KB	Output is correct
14	Correct	44 ms	18784 KB	Output is correct
15	Correct	75 ms	20452 KB	Output is correct
16	Correct	98 ms	25156 KB	Output is correct
17	Correct	117 ms	26444 KB	Output is correct
18	Correct	106 ms	26132 KB	Output is correct
19	Correct	125 ms	26556 KB	Output is correct
20	Correct	139 ms	26380 KB	Output is correct
21	Correct	105 ms	26112 KB	Output is correct
22	Correct	121 ms	26472 KB	Output is correct
23	Correct	117 ms	26360 KB	Output is correct
24	Correct	113 ms	26512 KB	Output is correct
25	Correct	117 ms	26332 KB	Output is correct
26	Correct	113 ms	26200 KB	Output is correct
27	Correct	103 ms	26016 KB	Output is correct
28	Correct	118 ms	26320 KB	Output is correct

Subtask #3

0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	18220 KB	Output is correct
2	Correct	38 ms	18220 KB	Output is correct
3	Correct	45 ms	19056 KB	Output is correct
4	Correct	47 ms	18860 KB	Output is correct
5	Correct	47 ms	18796 KB	Output is correct
6	Correct	43 ms	18760 KB	Output is correct
7	Correct	59 ms	18920 KB	Output is correct
8	Correct	43 ms	18756 KB	Output is correct
9	Correct	47 ms	18984 KB	Output is correct
10	Correct	44 ms	18760 KB	Output is correct
11	Correct	46 ms	18808 KB	Output is correct
12	Correct	66 ms	18816 KB	Output is correct
13	Correct	43 ms	18988 KB	Output is correct
14	Correct	44 ms	18784 KB	Output is correct
15	Correct	75 ms	20452 KB	Output is correct
16	Correct	98 ms	25156 KB	Output is correct
17	Correct	117 ms	26444 KB	Output is correct
18	Correct	106 ms	26132 KB	Output is correct
19	Correct	125 ms	26556 KB	Output is correct
20	Correct	139 ms	26380 KB	Output is correct
21	Correct	105 ms	26112 KB	Output is correct
22	Correct	121 ms	26472 KB	Output is correct
23	Correct	117 ms	26360 KB	Output is correct
24	Correct	113 ms	26512 KB	Output is correct
25	Correct	117 ms	26332 KB	Output is correct
26	Correct	113 ms	26200 KB	Output is correct
27	Correct	103 ms	26016 KB	Output is correct
28	Correct	118 ms	26320 KB	Output is correct
29	Runtime error	901 ms	262144 KB	Execution killed with signal 9
30	Halted	0 ms	0 KB	-