結果
問題 |
No.1947 質より種類数
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:04:51 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,831 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 76,444 KB |
最終ジャッジ日時 | 2025-06-12 21:06:06 |
合計ジャッジ時間 | 3,343 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 WA * 21 |
ソースコード
import sys def main(): N, V, C = map(int, sys.stdin.readline().split()) items = [] for _ in range(N): v, w = map(int, sys.stdin.readline().split()) items.append((v, w)) # Sort items by price (v) ascending, and by value (w) descending if prices are equal items.sort(key=lambda x: (x[0], -x[1])) # Precompute the sum of prices for the first k items sum_v_list = [] sum_v = 0 max_k = 0 for k in range(1, N + 1): if k - 1 >= len(items): break sum_v += items[k - 1][0] sum_v_list.append(sum_v) if sum_v > V: break max_k = k max_score = 0 for k in range(1, max_k + 1): current_sum_v = sum_v_list[k - 1] rem = V - current_sum_v if rem < 0: continue # Find the item with the highest efficiency (w/v) among the first k items best_eff = -1 best_v = 0 best_w = 0 for i in range(k): v_i, w_i = items[i] if v_i == 0: eff = float('inf') else: eff = (w_i, v_i) # Using tuple to compare as w_i/v_i # Compare eff with best_eff # eff is better if (w_i * best_v > best_w * v_i) if best_eff == -1 or (w_i * best_v > best_w * v_i) or (w_i * best_v == best_w * v_i and v_i < best_v): best_eff = (w_i, v_i) best_v = v_i best_w = w_i # Calculate additional items that can be bought with rem cnt = rem // best_v total_w = sum(items[i][1] for i in range(k)) + cnt * best_w score = k * C + total_w if score > max_score: max_score = score print(max(max_score, 0)) if __name__ == '__main__': main()