結果

問題 No.1947 質より種類数
ユーザー gew1fw
提出日時 2025-06-12 20:52:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,075 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,076 KB
実行使用メモリ 103,908 KB
最終ジャッジ日時 2025-06-12 20:56:32
合計ジャッジ時間 5,969 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 21 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import cmp_to_key

def main():
    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))

    # Sort by v ascending, then by efficiency descending for same v
    def compare_v(a, b):
        v_a, w_a = a
        v_b, w_b = b
        if v_a != v_b:
            return -1 if v_a < v_b else 1
        else:
            # Compare efficiency (w/v) descending
            lhs = w_a * v_b
            rhs = w_b * v_a
            return -1 if lhs > rhs else 1 if lhs < rhs else 0

    items_sorted = sorted(items, key=cmp_to_key(compare_v))
    v_sorted = [x[0] for x in items_sorted]
    w_sorted = [x[1] for x in items_sorted]

    # Compute prefix sums for v and w
    prefix_sum_v = [0] * (N + 1)
    prefix_sum_w = [0] * (N + 1)
    for i in range(N):
        prefix_sum_v[i+1] = prefix_sum_v[i] + v_sorted[i]
        prefix_sum_w[i+1] = prefix_sum_w[i] + w_sorted[i]

    max_total = 0

    for k in range(1, N+1):
        sum_v = prefix_sum_v[k]
        if sum_v > V:
            continue
        sum_w = prefix_sum_w[k]
        remaining = V - sum_v

        # Sort the selected k items by efficiency descending
        selected = items_sorted[:k]
        def compare_efficiency(a, b):
            v_a, w_a = a
            v_b, w_b = b
            lhs = w_a * v_b
            rhs = w_b * v_a
            return -1 if lhs > rhs else 1 if lhs < rhs else 0
        selected_sorted = sorted(selected, key=cmp_to_key(compare_efficiency))

        add_w = 0
        R = remaining
        for item in selected_sorted:
            vi, wi = item
            if R <= 0:
                break
            m = R // vi
            add_w += m * wi
            R -= m * vi

        total = sum_w + add_w + k * C
        if total > max_total:
            max_total = total

    print(max_total)

if __name__ == '__main__':
    main()
0