shin3110
@shin3110

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

どうすればTLE回避できますか?

Q&A

Closed

解決したいこと

以下のコードがTLEになります
制約は以下の通りです
1 ≤ N ≤ 50
1 ≤ X ≤ 10000
1 ≤ Ai ≤ 100
1 ≤ Bi ≤ 50
計算量が大丈夫かなと思っていたのですが、どこを直すべきですか?

該当するソースコード

n, x = map(int, input().split())

dp = [[False for _ in range(x+1)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    a, b = map(int, input().split())
    for j in [m for m in dp[i-1]]:
        for k in range(b+1):
            if j+k*a <= x:
                dp[i][j+k*a] = j+k*a

if dp[-1][-1]:
    print("Yes")
else:
    print("No")
0

No Answers yet.

Your answer might help someone💌