結果
問題 |
No.1430 Coup de Coupon
|
ユーザー |
![]() |
提出日時 | 2021-05-20 23:55:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 550 ms / 2,000 ms |
コード長 | 792 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 77,880 KB |
最終ジャッジ日時 | 2024-10-10 07:22:56 |
合計ジャッジ時間 | 7,058 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
n,C = map(int,input().split()) p = [int(input()) for _ in range(n)] const = [] per = [] for _ in range(C): t,x = map(int,input().split()) if t==1: const.append(x) else: per.append(x) p.sort(reverse=1) const.sort(reverse=1) per.sort(reverse=1) Lc,Lp = len(const), len(per) """ dp[i][j] = i 個処理してconst を j 枚使った, つまり per は i-j 枚使った """ INF = 10**18 dp = [INF]*(Lc+1) dp[0] = 0 for i,pi in enumerate(p): ndp = [x+pi for x in dp] for j in range(Lc+1): if i < j: break if i-j >= Lp: continue v = dp[j] + pi//100*(100-per[i-j]) ndp[j] = min(ndp[j],v) for j in range(1,Lc+1): v = dp[j-1] + max(pi-const[j-1],0) ndp[j] = min(ndp[j],v) dp = ndp #print(dp) print(min(dp))