ABC141 D - Powerful Discount Tickets (400)
DPでi番目まででj回割引した数を持とうとすると
$ O(NM^2)
で間に合わない
現在の価格に対してM回貪欲に最も高価な商品に割引をする
優先度付きキューを使うと一回あたり
$ O(\log N)
で済む
全体では
$ O(M \log N)
2回2で割った場合と1回4で割った場合で小数点以下切り捨ての結果は変わらない
問題:
https://atcoder.jp/contests/abc141/tasks/abc141_d
提出:
https://atcoder.jp/contests/abc141/submissions/7523231
#ABC141
#400pt
#D
#ABC
#AtCoder