Shopping in AtCoder store

题目描述

Takahashi 经营着 AtCoder 商店。 $N$ 位顾客光顾商店，商店里出售 $M$ 件商品。 第 $i$ 位 $(1\leq i\leq N)$ 顾客的购买意愿是 $B _ i$。 第 $j$ 件 $(1\leq j\leq M)$ 商品的价值是 $C _ j$。 Takahashi 为每件商品定价。 第 $i$ 位顾客当且仅当第 $j$ 件商品的价格 $P _ j$ 满足下列条件时会购买该商品：

$B _ i+C _ j\geq P _ j$。

对于每个 $j=1,2,\ldots,M$，当 Takahashi 设定价格以使该商品的销售额最大化时，求第 $j$ 件商品的总销售额。 第 $j$ 件商品的总销售额定义为 $P _ j$ 与购买第 $j$ 件商品的顾客数量的乘积。

输入格式

输入由标准输入按如下格式提供： $N$ $M$ $B _ 1$ $B _ 2$ $\ldots$ $B _ N$ $C _ 1$ $C _ 2$ $\ldots$ $C _ M$

输出格式

输出一行，包含第 $j$ 件商品的总销售额，按 $j=1,2,\ldots,M$ 的顺序，用空格分隔。

5 4
100 200 300 400 500
120 370 470 80

1280 2350 2850 1140

4 4
0 2 10 2
13 13 0 4

52 52 10 18

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

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

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

10000000000 10000000000 10000000000 10000000000 10000000000

提示

$1\leq N\leq2\times10^5$ $1\leq M\leq2\times10^5$ $0\leq B _ i\leq10^9\quad(1\leq i\leq N)$ $0\leq C _ i\leq10^9\quad(1\leq i\leq M)$ 输入中的所有数值均为整数。例如，他可以将第 $1$ 件商品的价格定为 $320$；则第 $2$、第 $3$、第 $4$ 和第 $5$ 位顾客会购买一件。 第 $1$ 件商品的总销售额将是 $1280$。 由于他无法使第 $1$ 件商品的总销售额超过 $1280$，因此要输出的第一个值是 $1280$。
可能有两位顾客具有相同的购买意愿。同样，也可能有两件商品具有相同的价值。
注意总销售额可能无法装入 32 位整数类型。

标签: AtCoder|abc289G

来源

AtCoder|abc289G