search

hxrxchang / atcoder

https://atcoder.jp/users/hxrxchang
0 stars 0 forks source link

D - Money in Hand #37

Open hxrxchang opened 2 months ago

hxrxchang commented 2 months ago

https://atcoder.jp/contests/abc286/tasks/abc286_d

持っているコインをフラットに持つと簡単。

N, X = map(int, input().split())
coins = []

for _ in range(N):
    A, B = map(int, input().split())
    for i in range(B):
        coins.append(A)

dp = [False] * (X + 1)
dp[0] = True

for coin in coins:
    tmp = dp[:]
    for i in range(1, X + 1):
        if i - coin >= 0:
            tmp[i] = dp[i] or dp[i - coin]
    dp = tmp

if dp[X]:
    print("Yes")
else:
    print("No")

https://atcoder.jp/contests/abc286/submissions/52977206