POH!Liteでめちゃめちゃ素直に実装してチューニングした結果

POH!Liteでめちゃめちゃ素直に実装してチューニングした結果

poh-lite.py

from itertools import starmap
m = input()
n = input()
cost = {0:0}
def update(x,y):
  s,t = q+x, r+y
  if not s in cost or cost[s]>t:
    return (s,t)
for i in range(n):
  q,r = map(int,raw_input().split())
  cost.update( filter(None,starmap(update,cost.iteritems())) )
print min( (cost[x] for x in cost.keys() if x>=m) )

TEST CASE 7で2.07秒
dict.updateに与えるシーケンスをfilterでリストにしているのがミソ