結果
問題 |
No.1947 質より種類数
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:10:20 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,785 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,480 KB |
実行使用メモリ | 93,964 KB |
最終ジャッジ日時 | 2025-06-12 16:10:31 |
合計ジャッジ時間 | 6,135 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 TLE * 1 -- * 25 |
ソースコード
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 items = [] for _ in range(N): v = int(input[idx]); idx += 1 w = int(input[idx]); idx += 1 items.append((v, w)) # Initialize DP table INF = -1 dp = [[INF] * (V + 1) for _ in range(N + 1)] dp[0][0] = 0 # 0 types, 0 cost, 0 value for i in range(N): v_i, w_i = items[i] # First, handle the case where we take at least one of the current item # We need to iterate backwards to avoid overwriting the dp array prematurely for k in range(N - 1, -1, -1): for v in range(V, -1, -1): if dp[k][v] == INF: continue new_v = v + v_i if new_v > V: continue new_k = k + 1 if dp[new_k][new_v] < dp[k][v] + w_i: dp[new_k][new_v] = dp[k][v] + w_i # Then, apply the unbounded knapsack for additional items of the same type # This does not increase the type count k for k in range(N + 1): for v in range(V + 1 - v_i): if dp[k][v] == INF: continue if dp[k][v + v_i] < dp[k][v] + w_i: dp[k][v + v_i] = dp[k][v] + w_i max_satisfaction = 0 for k in range(N + 1): max_val = max([val for val in dp[k] if val != INF], default=-1) if max_val == -1: continue satisfaction = max_val + k * C if satisfaction > max_satisfaction: max_satisfaction = satisfaction print(max_satisfaction) if __name__ == '__main__': main()