結果

問題 No.1947 質より種類数
ユーザー gew1fw
提出日時 2025-06-12 20:57:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,975 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 77,252 KB
最終ジャッジ日時 2025-06-12 21:01:07
合計ジャッジ時間 3,566 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, then by w descending to maximize sum_w when v is the same
items.sort(key=lambda x: (x[0], -x[1]))

# Precompute cumulative sums of v and w
cum_v = [0] * (n + 1)
cum_w = [0] * (n + 1)
for i in range(n):
    cum_v[i + 1] = cum_v[i] + items[i][0]
    cum_w[i + 1] = cum_w[i] + items[i][1]

# Precompute the most efficient item (max w/v) for each k
max_eff = [(0, 0)] * (n + 1)  # (v, w)
for k in range(1, n + 1):
    if k == 1:
        current_v, current_w = items[0]
        max_eff[k] = (current_v, current_w)
    else:
        prev_v, prev_w = max_eff[k - 1]
        current_v, current_w = items[k - 1]

        # Compare current item with previous max_eff
        current_eff_num = current_w * prev_v
        prev_eff_num = prev_w * current_v

        if current_eff_num > prev_eff_num:
            max_eff[k] = (current_v, current_w)
        elif current_eff_num < prev_eff_num:
            max_eff[k] = (prev_v, prev_w)
        else:
            # Same efficiency, choose smaller v
            if current_v < prev_v:
                max_eff[k] = (current_v, current_w)
            elif current_v > prev_v:
                max_eff[k] = (prev_v, prev_w)
            else:
                # Same v, choose higher w
                if current_w > prev_w:
                    max_eff[k] = (current_v, current_w)
                else:
                    max_eff[k] = (prev_v, prev_w)

max_satisfaction = 0
for k in range(1, n + 1):
    if cum_v[k] > V:
        continue
    rem = V - cum_v[k]
    best_v, best_w = max_eff[k]
    if best_v == 0:
        continue  # avoid division by zero, though v >=1 per constraints
    cnt = rem // best_v
    total_w = cum_w[k] + cnt * best_w
    satisfaction = k * C + total_w
    if satisfaction > max_satisfaction:
        max_satisfaction = satisfaction

print(max_satisfaction)
0