AT_abc289_g [ABC289G] Shopping in AtCoder store

题目描述

高桥君经营着 AtCoder 商店。AtCoder 商店有 $N$ 位顾客光临，售卖 $M$ 种商品。第 $i$ 位顾客（$1\leq i\leq N$）有一个购买意愿 $B_i$。第 $j$ 种商品（$1\leq j\leq M$）的商品价值为 $C_j$。

高桥君需要为每个商品定价。第 $i$ 位顾客只会购买第 $j$ 种商品，当且仅当该商品的价格 $P_j$ 满足以下条件：

• $B_i + C_j \geq P_j$

每个顾客对每种商品最多只会购买 $1$ 件。

请你对于 $j=1,2,\ldots,M$，求出当高桥君为第 $j$ 种商品定价，使得其销售额最大时，该商品的最大销售额。这里，第 $j$ 种商品的销售额定义为 $P_j$ 乘以购买该商品的顾客人数。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$B_1$ $B_2$ $\ldots$ $B_N$
$C_1$ $C_2$ $\ldots$ $C_M$

输出格式

请输出 $M$ 个整数，第 $j$ 个数表示第 $j$ 种商品的最大销售额。各数之间用空格隔开，输出一行。

输入输出样例 #1

输入 #1

5 4
100 200 300 400 500
120 370 470 80

输出 #1

1280 2350 2850 1140

输入输出样例 #2

输入 #2

4 4
0 2 10 2
13 13 0 4

输出 #2

52 52 10 18

输入输出样例 #3

输入 #3

12 15
16 592 222 983 729 338 747 61 451 815 838 281
406 319 305 519 317 590 507 946 365 5 673 478 340 176 2

输出 #3

6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655

输入输出样例 #4

输入 #4

5 5
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

输出 #4

10000000000 10000000000 10000000000 10000000000 10000000000

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $0\leq B_i\leq 10^9\quad(1\leq i\leq N)$
• $0\leq C_j\leq 10^9\quad(1\leq j\leq M)$
• 所有输入均为整数

样例解释 1

例如，将第 $1$ 种商品的价格定为 $320$ 时，第 $2,3,4,5$ 位顾客会购买。此时第 $1$ 种商品的销售额为 $1280$。无法使第 $1$ 种商品的销售额超过 $1280$，因此输出的第 $1$ 个值应为 $1280$。

样例解释 2

也可能存在有 $2$ 位顾客购买意愿相同，或有 $2$ 种商品商品价值相同的情况。

样例解释 4

请注意，销售额可能会超过 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译