結果
問題 | No.1037 exhausted |
ユーザー |
|
提出日時 | 2022-03-27 23:13:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 559 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 82,120 KB |
実行使用メモリ | 77,404 KB |
最終ジャッジ日時 | 2024-11-06 16:12:08 |
合計ジャッジ時間 | 3,128 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
n,V,l = map(int,input().split())XVW = [list(map(int,input().split())) for i in range(n)]inf = 10**15dp = [inf]*(V+1)dp[V] = 0now = 0for x,v,w in XVW:dif = x-nownow = xndp = [inf]*(V+1)mi = inffor j in range(dif,V+1)[::-1]:if dp[j] == inf:continuemi = min(mi,dp[j])ndp[j-dif] = min(ndp[j-dif],dp[j])ndp[min(j-dif+v,V)] = min(ndp[min(j-dif+v,V)],dp[j]+w)dp = ndpdif = l-nowans = inffor i in range(dif,V+1):ans = min(ans,dp[i])if ans == inf:ans = -1print(ans)