제출 #1268111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268111		joesephdiver	Mecho (IOI09_mecho)	Pypy 3	19 / 100	433 ms	85440 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]
q = deque([M])

while q:
    x, y = q.popleft()
    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])

sol = -1
for x in range(N):
    for y in range(N):
        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] == 'D':
                sol = max(sol, distdiff[x][y])
print(sol)

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'mecho.py'...

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

=======

• Subtask 1: 19 / 100