結果

問題 No.1430 Coup de Coupon
コンテスト
ユーザー titia
提出日時 2026-02-16 05:54:51
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 337 ms / 2,000 ms
コード長 803 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 356 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 77,236 KB
最終ジャッジ日時 2026-02-16 05:54:59
合計ジャッジ時間 6,361 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N,C=list(map(int,input().split()))

P=[int(input()) for i in range(N)]

X=[]
Y=[]

for i in range(C):
    t,x=list(map(int,input().split()))

    if t==1:
        X.append(x)
    else:
        Y.append(x)

P.sort(reverse=True)
X.sort(reverse=True)
Y.sort(reverse=True)

DP=[0]

for i in range(N):
    NDP=[1<<60]*(i+2)

    money=P[i]

    for j in range(i+1):
        # 今まで、Xをj-1個使った。
        # つまり、次の使うXはX[j]
        # YならばY[i-j]

        if j<len(X):
            plus=max(money-X[j],0)
            NDP[j+1]=min(NDP[j+1],DP[j]+plus)

        if i-j<len(Y):
            plus=money*(100-Y[i-j])//100
            NDP[j]=min(NDP[j],DP[j]+plus)

        NDP[j]=min(NDP[j],DP[j]+money)

    DP=NDP

print(min(DP))
0