結果

問題 No.1947 質より種類数
ユーザー lam6er
提出日時 2025-03-31 17:45:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,519 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 71,412 KB
最終ジャッジ日時 2025-03-31 17:45:59
合計ジャッジ時間 3,036 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    V = int(input[ptr])
    ptr += 1
    C = int(input[ptr])
    ptr += 1

    items = []
    for _ in range(N):
        v = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        items.append((v, w))

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

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

    # Find k_max using bisect
    k_max = 0
    left, right = 0, n
    while left <= right:
        mid = (left + right) // 2
        if mid > n:
            right = mid - 1
            continue
        if sv[mid] <= V:
            k_max = mid
            left = mid + 1
        else:
            right = mid - 1
    k_max = min(k_max, n)

    max_total = 0
    # List to maintain items sorted by efficiency (w/v) in descending order
    sorted_by_efficiency = []

    for k in range(1, k_max + 1):
        sum_v = sv[k]
        if sum_v > V:
            continue  # Not possible, but due to k_max, this shouldn't happen
        rem = V - sum_v
        sum_initial_w = sw[k]
        # Get the current item (k-th item in first k items, which is items[k-1])
        v, w = items[k - 1]
        efficiency = w / v

        # Find insertion position in sorted_by_efficiency using custom bisect for descending order
        left = 0
        right = len(sorted_by_efficiency)
        while left < right:
            mid = (left + right) // 2
            if sorted_by_efficiency[mid][2] > efficiency:
                left = mid + 1
            else:
                right = mid
        pos = left
        # Insert the new item into the sorted list
        sorted_by_efficiency.insert(pos, (v, w, efficiency))

        # Calculate additional w using the remaining money
        current_rem = rem
        sum_additional = 0
        for item in sorted_by_efficiency:
            vi, wi, eff = item
            if current_rem <= 0:
                break
            cnt = current_rem // vi
            sum_additional += cnt * wi
            current_rem -= cnt * vi

        total = C * k + sum_initial_w + sum_additional
        if total > max_total:
            max_total = total

    # Handle k=0 case (no items bought)
    print(max_total)

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