Submission #647162

#	Time	Username	Problem	Language	Result	Execution time	Memory
647162		beaconmc	The Kingdom of JOIOI (JOI17_joioi)	Pypy 3	60 / 100	4072 ms	221204 KiB

joioi

U=float
T=int
S=map
R=max
K=min
A=range
import sys
input=lambda:sys.stdin.readline().strip()
E,C=S(T,input().split())
F=[list(S(T,input().split()))for B in A(E)]
N=[[0 for B in A(C)]for B in A(E)]
L=-1
for J in A(E):
	for M in A(C):L=R(L,F[J][M]);N[J][M]=F[E-J-1][C-M-1]
G=[[1000000000 for B in A(C)]for B in A(E)]
H=[[1000000000 for B in A(C)]for B in A(E)]
def O():
	for B in A(E-1,-1,-1):
		G[B][0]=F[B][0]
		for D in A(1,C):G[B][D]=K(G[B][D-1],F[B][D])
		if B!=E-1:
			for D in A(C):G[B][D]=K(G[B][D],G[B+1][D])
	for B in A(E-1,-1,-1):
		H[B][C-1]=F[B][C-1]
		for D in A(C-2,-1,-1):H[B][D]=K(H[B][D+1],F[B][D])
		if B!=E-1:
			for D in A(C-1,-1,-1):H[B][D]=K(H[B][D],H[B+1][D])
def P(a):
	M=True;N='inf';B=U(N);D=-1
	for I in A(E):
		for J in A(C):
			if L-G[I][J]>a:B=K(B,F[I][J]);D=R(D,F[I][J])
	if D-B<=a:return M
	B=U(N);D=-1
	for I in A(E):
		for J in A(C):
			if L-H[I][J]>a:B=K(B,F[I][J]);D=R(D,F[I][J])
	if D-B<=a:return M
	return False
O()
B=0
D=L
while B<D:
	I=(B+D)//2
	if P(I):D=I
	else:B=I+1
Q=B
F=N
G=[[1000000000 for B in A(C)]for B in A(E)]
H=[[1000000000 for B in A(C)]for B in A(E)]
O()
B=0
D=Q
while B<D:
	I=(B+D)//2
	if P(I):D=I
	else:B=I+1
print(K(Q,B))

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