結果
問題 |
No.1947 質より種類数
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:55:07 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,067 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 82,964 KB |
実行使用メモリ | 77,284 KB |
最終ジャッジ日時 | 2025-06-12 15:55:33 |
合計ジャッジ時間 | 21,980 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 TLE * 4 |
ソースコード
def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx +=1 V = int(input[idx]); idx +=1 C = int(input[idx]); idx +=1 types = [] for _ in range(N): v = int(input[idx]); idx +=1 w = int(input[idx]); idx +=1 types.append((v, w)) # Initialize DP dp = [-float('inf')] * (V + 1) dp[0] = 0 for v_i, w_i in types: # Step 1: 0-1 step (activate the type) for c in range(V, v_i - 1, -1): if dp[c - v_i] != -float('inf'): if dp[c] < dp[c - v_i] + w_i + C: dp[c] = dp[c - v_i] + w_i + C # Step 2: Unbounded step (additional items) for c in range(v_i, V + 1): if dp[c - v_i] != -float('inf'): if dp[c] < dp[c - v_i] + w_i: dp[c] = dp[c - v_i] + w_i max_satisfaction = 0 for c in range(V + 1): if dp[c] > max_satisfaction: max_satisfaction = dp[c] print(max_satisfaction) if __name__ == "__main__": main()