結果

問題 No.1430 Coup de Coupon
ユーザー lam6er
提出日時 2025-04-15 21:00:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,220 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 465,724 KB
最終ジャッジ日時 2025-04-15 21:06:06
合計ジャッジ時間 4,188 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, C = int(input[idx]), int(input[idx+1])
    idx +=2
    P = []
    for _ in range(N):
        P.append(int(input[idx]))
        idx +=1
    coupons = []
    for _ in range(C):
        T = int(input[idx])
        X = int(input[idx+1])
        idx +=2
        coupons.append((T, X))
    
    # Precompute for each coupon the list of (savings, product) sorted descending
    coupon_product_savings = []
    for j in range(C):
        Tj, Xj = coupons[j]
        savings_list = []
        for i in range(N):
            Pi = P[i]
            if Tj == 1:
                price = max(Pi - Xj, 0)
            else:
                price = Pi * (100 - Xj) // 100
            savings = Pi - price
            if savings < 0:
                savings = 0  # since using coupon is worse than not using
            savings_list.append(( -savings, i ))  # use negative for ascending sort later
        # Sort by savings descending, then product index ascending
        savings_list.sort()
        # Convert back to positive savings and original order
        sorted_list = []
        max_saving = 0
        for s, i in savings_list:
            saving = -s
            if saving > max_saving:
                max_saving = saving
            sorted_list.append( (i, saving) )
        coupon_product_savings.append( (max_saving, j, sorted_list) )
    
    # Sort coupons by max_saving descending, then coupon index to break ties
    coupon_product_savings.sort( key=lambda x: (-x[0], x[1]) )
    
    used_products = set()
    used_coupons = set()
    total_saving = 0
    
    for cp in coupon_product_savings:
        max_save, j, sorted_list = cp
        if j in used_coupons:
            continue
        for (i, save) in sorted_list:
            if save <=0:
                break  # since sorted descending, no more positive savings
            if i not in used_products and j not in used_coupons:
                total_saving += save
                used_products.add(i)
                used_coupons.add(j)
                break
    
    total_original = sum(P)
    print( total_original - total_saving )
    
if __name__ == '__main__':
    main()
0