結果

問題 No.1430 Coup de Coupon
ユーザー gew1fw
提出日時 2025-06-12 15:24:57
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,833 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 750,844 KB
最終ジャッジ日時 2025-06-12 15:25:11
合計ジャッジ時間 4,033 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    P = []
    for _ in range(N):
        P.append(int(input[ptr]))
        ptr += 1

    coupons = []
    for _ in range(C):
        Tj = int(input[ptr])
        Xj = int(input[ptr + 1])
        coupons.append((Tj, Xj))
        ptr += 2

    # Precompute for each coupon j, a list of (D, i) sorted descending by D
    coupon_products = []
    for j in range(C):
        T, X = coupons[j]
        products = []
        for i in range(N):
            Pi = P[i]
            if T == 1:
                new_price = max(Pi - X, 0)
                D = Pi - new_price
            else:
                new_price = (Pi * (100 - X)) // 100
                D = Pi - new_price
            products.append((D, i))
        # Sort products for this coupon in descending order of D
        products.sort(reverse=True, key=lambda x: x[0])
        coupon_products.append(products)

    # Prepare list to sort coupons by their maximum D
    max_discounts = []
    for j in range(C):
        if coupon_products[j]:
            max_d = coupon_products[j][0][0]
            max_discounts.append((-max_d, j))  # Negative for ascending sort
        else:
            max_discounts.append((0, j))  # No products, just in case

    # Sort coupons by max discount in descending order
    max_discounts.sort()
    sorted_coupons = [j for _, j in max_discounts]

    assigned = [False] * N
    total_discount = 0

    for j in sorted_coupons:
        for d, i in coupon_products[j]:
            if not assigned[i]:
                assigned[i] = True
                total_discount += d
                break

    total_cost = sum(P) - total_discount
    print(total_cost)

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