問題一覧 > 通常問題

No.2770 Coupon Optimization

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 69
作問者 : srjywrdnprkt / テスター : hahho
お気に入りにしたユーザー ProblemId : 10360 / 自分の提出
問題文最終更新日: 2025-03-05 16:46:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 431 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。