ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1119. Метро

accepted python
Послано stariy_bog 20 фев 2025 21:04
# works on pypy

import sys

n, m = sys.stdin.readline().split()
n, m = int(n), int(m)
k = int(sys.stdin.readline())
can_diag = {tuple(map(int, sys.stdin.readline().split())):0 for _ in range(k)}
city_map = [[0]*(n+1) for _ in range(m+1)]
for i in range(n+1):
    city_map[0][i] = i*100
for i in range(m+1):
    city_map[i][0] = i*100
for i in range(1, m+1):
    for j in range(1, n+1):
        if (j, i) in can_diag:
            city_map[i][j] = 100*(2**0.5)+city_map[i-1][j-1]
        else:
            city_map[i][j] = 100+min(city_map[i][j-1], city_map[i-1][j])

print(round(city_map[-1][-1]))