結果

問題 No.1947 質より種類数
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:49:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,692 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 82,528 KB
実行使用メモリ 77,296 KB
最終ジャッジ日時 2025-03-20 18:50:44
合計ジャッジ時間 3,458 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, V, C = map(int, input().split())
items = []
for _ in range(n):
    v, w = map(int, input().split())
    items.append((v, w))

# Sort items by v ascending, and by w descending for same v
items.sort(key=lambda x: (x[0], -x[1]))

# Precompute prefix sums for min_v and sum_w
sum_v_min = [0] * (n + 1)
sum_w_min = [0] * (n + 1)
for k in range(1, n + 1):
    sum_v_min[k] = sum_v_min[k - 1] + items[k - 1][0]
    sum_w_min[k] = sum_w_min[k - 1] + items[k - 1][1]

# Precompute max efficiency items for each k
max_eff_v = [0] * (n + 1)
max_eff_w = [0] * (n + 1)
current_max_v = None
current_max_w = None

for k in range(1, n + 1):
    v, w = items[k - 1]
    if k == 1:
        current_max_v = v
        current_max_w = w
    else:
        a, b = w, v
        c, d = current_max_w, current_max_v
        # Compare (a/b) vs (c/d)
        if a * d > c * b:
            current_max_v = v
            current_max_w = w
        elif a * d == c * b:
            if v < current_max_v:
                current_max_v = v
                current_max_w = w
            elif v == current_max_v and w > current_max_w:
                current_max_w = w
    max_eff_v[k] = current_max_v
    max_eff_w[k] = current_max_w

max_satisfaction = 0

# Consider k from 0 to n
for k in range(0, n + 1):
    if k == 0:
        current = 0
    else:
        if sum_v_min[k] > V:
            continue
        rest = V - sum_v_min[k]
        best_v = max_eff_v[k]
        best_w = max_eff_w[k]
        x = rest // best_v
        add_value = x * best_w
        total_w = sum_w_min[k] + add_value
        current = total_w + C * k
    if current > max_satisfaction:
        max_satisfaction = current

print(max_satisfaction)
0