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

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

WA#10. Non DP Solution. Python 2.7.
Послано m1cky 3 май 2015 01:46
Could anyone give me a hint on my mistake, please?

# -*- coding: utf-8 -*-

import math
import sys

c = math.sqrt(100**2 + 100**2)

n, m = sys.stdin.readline().strip().split()
n, m = int(n), int(m)

can_be_crossed_cnt = int(sys.stdin.readline().strip())
can_be_crossed = []
for line in sys.stdin.readlines():
    i, j = line.strip().split()
    i, j = int(i), int(j)
    can_be_crossed.append((i,j))


sorted_by_x = sorted(can_be_crossed, reverse=True)
sorted_by_y = sorted(can_be_crossed, key=lambda (x,y): (y,x), reverse=True)

maxs = []
for can_be_crossed in (sorted_by_x, sorted_by_y):
    last = None
    can_be_visited_cnt = 0
    for (i,j) in can_be_crossed:
        if last is None:
            if i <= n and j <= m:
                can_be_visited_cnt = 1
                last = (i, j)
        else:
            last_i, last_j = last
            if i < last_i and j < last_j:
                can_be_visited_cnt += 1
                last = (i, j)
                continue
    maxs.append(can_be_visited_cnt)

distance = ((n+m)-2*max(maxs))*100 + max(maxs) * c
sys.stdout.write(str(int(round(distance))))