結果
問題 | No.1583 Building Blocks |
ユーザー |
|
提出日時 | 2021-07-02 22:03:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 644 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 76,112 KB |
最終ジャッジ日時 | 2024-09-14 02:46:30 |
合計ジャッジ時間 | 3,753 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) n = int(input()) ws = [list(map(int, input().split())) for _ in range(n)] ws.sort(key=lambda i: sum(i)) inf = 10**12 dp = [inf]*(n+1) dp[0] = 0 for i in range(n): w,s = ws[i] ndp = [inf]*(n+1) for j in range(n): if dp[j]<=s: ndp[j+1] = min(ndp[j+1], dp[j]+w) ndp[j] = min(ndp[j], dp[j]) dp = ndp for i in range(n+1)[::-1]: if dp[i]<inf: break ans = i print(ans)