Submission #647161

#	Time	Username	Problem	Language	Result	Execution time	Memory
647161		beaconmc	The Kingdom of JOIOI (JOI17_joioi)	Pypy 3	60 / 100	4029 ms	221760 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)]
mx=-1
for i in range(n):
	for j in range(m):mx=max(mx,grid[i][j]);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):
	B=True;A='inf';mini=float(A);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 B
	mini=float(A);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 B
	return False
setup()
lo=0
hi=mx
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: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40