結果

問題 No.1430 Coup de Coupon
ユーザー lam6er
提出日時 2025-04-15 21:18:41
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 915 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 856,968 KB
最終ジャッジ日時 2025-04-15 21:24:30
合計ジャッジ時間 4,344 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 6 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff #

n, c = map(int, input().split())
prices = [int(input()) for _ in range(n)]
coupons = [tuple(map(int, input().split())) for _ in range(c)]

original_total = sum(prices)
savings_list = []

for i in range(n):
    p = prices[i]
    for j in range(c):
        t, x = coupons[j]
        if t == 1:
            discounted = max(p - x, 0)
        else:
            discounted = (p * (100 - x)) // 100
        saving = p - discounted
        if saving > 0:
            savings_list.append((-saving, i, j))  # Negative for ascending sort

# Sort by descending savings (handled by negative)
savings_list.sort()

used_products = set()
used_coupons = set()
total_savings = 0

for s in savings_list:
    saving = -s[0]
    i = s[1]
    j = s[2]
    if i not in used_products and j not in used_coupons:
        total_savings += saving
        used_products.add(i)
        used_coupons.add(j)

print(original_total - total_savings)
0