結果

問題 No.1947 質より種類数
ユーザー gew1fw
提出日時 2025-06-12 16:12:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,831 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 76,988 KB
最終ジャッジ日時 2025-06-12 16:13:05
合計ジャッジ時間 3,686 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0