제출 #647169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647169		beaconmc	The Kingdom of JOIOI (JOI17_joioi)	Pypy 3	0 / 100	70 ms	20504 KiB

joioi

from copy import *
import sys
input = lambda: sys.stdin.readline().strip()
 
n,m = map(int, input().split())
 
grid = [list(map(int, input().split()))for i in range(n)]
grid2 = [[0 for i in range(m)]for i in range(n)]
 
for i in range(n):
    for j in range(m):
        grid2[i][j] = grid[n-i-1][m-j-1]
 
 
minmaxl = [[1000000000 for i in range(m)]for i in range(n)]
minmaxr = [[1000000000 for i in range(m)]for i in range(n)]
 
def setup():
 
    for i in range(n-1,-1,-1):
        minmaxl[i][0] = grid[i][0]
        for j in range(1,m):
            minmaxl[i][j] = min(minmaxl[i][j-1], grid[i][j])
 
        if i != n-1:
            for j in range(m):
                minmaxl[i][j] = min(minmaxl[i][j], minmaxl[i+1][j])
 
    for i in range(n-1,-1,-1):
        minmaxr[i][m-1] = grid[i][m-1]
        for j in range(m-2,-1,-1):
            minmaxr[i][j] = min(minmaxr[i][j+1], grid[i][j])
 
        if i != n-1:
            for j in range(m-1,-1,-1):
                minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j])
 
def check(a):
 
    mini = float("inf")
    maxi = -1
    for i in range(n):
        for j in range(m):
            if mx - minmaxl[i][j] > a:
                mini = min(mini, grid[i][j])
                maxi = max(maxi, grid[i][j])
    if maxi - mini <= a:
        return True
    
 
    mini = float("inf")
    maxi = -1
    for i in range(n):
        for j in range(m):
            if mx - minmaxr[i][j] > a:
                mini = min(mini, grid[i][j])
                maxi = max(maxi, grid[i][j])
    if maxi - mini <= a:
        return True
    return False
 
setup()
lo = 0
hi = 1000000000
while (lo<hi):
    mid = (lo+hi)//2
    if check(mid):
        hi = mid
    else:
        lo = mid+1
ans = lo
grid = grid2
 
minmaxl = [[1000000000 for i in range(m)]for i in range(n)]
minmaxr = [[1000000000 for i in range(m)]for i in range(n)]
setup()
lo = 0
hi = ans
 
while (lo<hi):
    mid = (lo+hi)//2
    if check(mid):
        hi = mid
    else:
        lo = mid+1
print(min(ans,lo))

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