No.2770 Coupon Optimization
タグ : / 解いたユーザー数 69
作問者 :
srjywrdnprkt
/ テスター :
hahho
Problem Statement
Yukio is planning to buy some takoyaki makers at Yuki Electronics in order to hold a takoyaki party.
Yuki Electronics sells $N$ takoyaki makers, and the price of the $i$-th takoyaki maker is $A_i$ yen. Here, it is guaranteed that $A_i$ is a multiple of $100$ for every integer $i$ satisfying $1\leq i \leq N$.
Yukio has $M$ coupons. Using the $i$-th coupon, he can buy a takoyaki maker priced at $x$ yen at a $B_i$ % discount. That is, he can buy it for $\frac{100-B_i}{100}x$ yen.
However, he cannot use multiple coupons on $1$ takoyaki maker, and he cannot reuse a coupon that has already been used.
For each of $k=1,\cdots N$, find the minimum amount of money required for Yukio to buy $k$ takoyaki makers when he uses the coupons optimally.
Input
$N\ M$ $A_1\ \cdots\ A_N$ $B_1\ \cdots\ B_M$
All inputs are integers and satisfy the following constraints.
- $1\leq N\leq 2\times 10^5$
- $1 \leq M \leq 2\times 10^5$
- $100 \leq A_i \leq 10^9$
- $A_i$ is a multiple of $100$
- $1 \leq B_i \leq 99$
Output
Output $N$ lines. On the $k$-th line, output the minimum amount of money required for Yukio to buy $k$ takoyaki makers.
Sample
Sample 1
Input
3 2 2000 1500 1700 10 15
Output
1275 2795 4730
Consider the case $k=2$. He buys the $2$-nd takoyaki maker using the $1$-st coupon, and the $3$-rd takoyaki maker using the $2$-nd coupon.
The cost in this case is $\frac{100-10}{100}\times 1500+\frac{100-15}{100}\times 1700 = 2795$ yen, which is the minimum.Sample
Sample 2
Input
3 5 100 100000 1000000000 31 41 52 95 89
Output
5 5011 50011048
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。