Submission #1268113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268113		joesephdiver	Mecho (IOI09_mecho)	Pypy 3	19 / 100	406 ms	84708 KiB

mecho

from collections import deque
from math import ceil

N, S = map(int, input().split())

a = [input() for _ in range(N)]

dist = [[-1]*N for x in range(N)]
q = deque()

for x in range(N):
    for y in range(N):
        if a[x][y] == 'H':
            q.append((x, y))
            dist[x][y] = 0
        elif a[x][y] == 'M':
            M = (x, y)
        elif a[x][y] == 'D':
            D = (x, y)
            
while q:
    x, y = q.popleft()
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if 0 <= x+dx < N and 0 <= y+dy < N and a[x+dx][y+dy] in 'GM' and dist[x+dx][y+dy] == -1:
            dist[x+dx][y+dy] = dist[x][y]+1
            q.append((x+dx, y+dy))
            
distM = [[float('inf')]*N for x in range(N)]
distdiff = [[float('-inf')]*N for x in range(N)]
distM[M[0]][M[1]], distdiff[M[0]][M[1]] = 0, dist[x][y]
distdiff[D[0]][D[1]] = -1
q = deque([M])

while q:
    x, y = q.popleft()
    if a[x][y] != 'D':
        distdiff[x][y] = min(distdiff[x][y], dist[x][y]-ceil(distM[x][y]/S))
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if 0 <= x+dx < N and 0 <= y+dy < N and a[x+dx][y+dy] in 'GD' and distM[x][y]+1 <= distM[x+dx][y+dy]:
            if distM[x+dx][y+dy] == float('inf'):
                distM[x+dx][y+dy] = distM[x][y]+1
                q.append((x+dx, y+dy))
            distdiff[x+dx][y+dy] = max(distdiff[x][y], distdiff[x+dx][y+dy])

print(distdiff[D[0]][D[1]])

Compilation message (stdout)

Compiling 'mecho.py'...

=======
  adding: __main__.pyc (deflated 53%)

=======

• Subtask 1: 19 / 100