oj.uz

Submission #647077

# Submission time Handle Problem Language Result Execution time Memory
647077 2022-10-01T14:26:57 Z beaconmc The Kingdom of JOIOI (JOI17_joioi) PyPy 3
0 / 100
 66 ms 19892 KB 
n,m = map(int, input().split())

grid = [list(map(int, input().split()))for i in range(n)]

minmaxl = [[[float("inf"), -1]for i in range(m)]for i in range(n)]


for i in range(n-1,-1,-1):
    minmaxl[i][0] = [grid[i][0], grid[i][0]]
    for j in range(1,m):
        minmaxl[i][j][0] = min(minmaxl[i][j-1][0], grid[i][j])
        minmaxl[i][j][1] = max(minmaxl[i][j-1][1], grid[i][j])
    if i != n-1:
        for j in range(m):
            minmaxl[i][j][0] = min(minmaxl[i][j][0], minmaxl[i+1][j][0])
            minmaxl[i][j][1] = max(minmaxl[i][j][1], minmaxl[i+1][j][1])

minmaxr = [[[float("inf"), -1]for i in range(m)]for i in range(n)]
for i in range(n-1,-1,-1):
    minmaxr[i][m-1] = [grid[i][m-1], grid[i][m-1]]
    for j in range(m-2,-1,-1):
        minmaxr[i][j][0] = min(minmaxr[i][j+1][0], grid[i][j])
        minmaxr[i][j][1] = max(minmaxr[i][j+1][1], grid[i][j])
    if i != n-1:
        for j in range(m-1,-1,-1):
            minmaxr[i][j][0] = min(minmaxr[i][j][0], minmaxr[i+1][j][0])
            minmaxr[i][j][1] = max(minmaxr[i][j][1], minmaxr[i+1][j][1])

def check(a):
    visited = [[False for i in range(m)]for i in range(n)]
    mini = float("inf")
    maxi = -1
    for i in range(n):
        for j in range(m):
            if minmaxl[i][j][1] - minmaxl[i][j][0] <= a:
                visited[i] = True
            else:
                mini = min(mini, grid[i][j])
                maxi = max(maxi, grid[i][j])
    if maxi - mini <= a:
        return True
    
    visited = [[False for i in range(m)]for i in range(n)]
    mini = float("inf")
    maxi = -1
    for i in range(n):
        for j in range(m):
            if minmaxr[i][j][1] - minmaxr[i][j][0] <= a:
                visited[i] = True
            else:
                mini = min(mini, grid[i][j])
                maxi = max(maxi, grid[i][j])
    if maxi - mini <= a:
        return True
    return False

lo = 0
hi = 1000000001
while (lo<hi):
    mid = (lo+hi)//2
    if check(mid):
        hi = mid
    else:
        lo = mid+1
print(lo)

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19892 KB Output is correct
2 Correct 46 ms 18844 KB Output is correct
3 Correct 57 ms 19224 KB Output is correct
4 Correct 63 ms 19696 KB Output is correct
5 Correct 66 ms 19368 KB Output is correct
6 Incorrect 52 ms 19180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19892 KB Output is correct
2 Correct 46 ms 18844 KB Output is correct
3 Correct 57 ms 19224 KB Output is correct
4 Correct 63 ms 19696 KB Output is correct
5 Correct 66 ms 19368 KB Output is correct
6 Incorrect 52 ms 19180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19892 KB Output is correct
2 Correct 46 ms 18844 KB Output is correct
3 Correct 57 ms 19224 KB Output is correct
4 Correct 63 ms 19696 KB Output is correct
5 Correct 66 ms 19368 KB Output is correct
6 Incorrect 52 ms 19180 KB Output isn't correct
7 Halted 0 ms 0 KB -