|
|
back to boardWA#10. Non DP Solution. Python 2.7. Posted by m1cky 3 May 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)))) |
|
|