結果
問題 | No.1430 Coup de Coupon |
ユーザー |
![]() |
提出日時 | 2021-03-14 14:44:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 698 ms / 2,000 ms |
コード長 | 1,037 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 272,744 KB |
最終ジャッジ日時 | 2024-11-06 04:41:46 |
合計ジャッジ時間 | 8,371 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
mod = 1000000007eps = 10**-9inf = 10**18def main():import sysinput = sys.stdin.readlineN, M = map(int, input().split())P = []for _ in range(N):P.append(int(input()))C1 = []C2 = []for _ in range(M):t, x = map(int, input().split())if t == 1:C1.append(x)else:C2.append(x)C1.sort(reverse=True)C2.sort(reverse=True)P.sort(reverse=True)if len(C1) + len(C2) < N:for _ in range(N - M):C2.append(0)M = Ndp = [[inf] * (len(C1) + 1) for _ in range(N+1)]dp[0][0] = 0for i in range(N):p = P[i]for j in range(len(C1) + 1):# use C1if j != len(C1):dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + max(0, p - C1[j]))# use C2if 0 <= i-j < len(C2):dp[i+1][j] = min(dp[i+1][j], dp[i][j] + p * (100 - C2[i - j]) // 100)print(min(dp[-1]))if __name__ == '__main__':main()