[ABC144E] Gluttony
题意翻译
【题目描述】
高桥君参加大胃王比赛。比赛由 $N$ 人组成的团队为基本单位参赛,高桥君的队伍的队员从 $1\sim N$ 编号。第 $i$ 名队员的消化代价为 $A_i$。
比赛有 $N$ 种不同的食物,每位队员需要负责吃掉其中一种食物,不能有两名队员吃同一种食物,也不能让一名队员吃多与一种食物。第 $j$ 种食物的难吃程度为 $F_j$。 消化代价 $x$ 的队员吃完难吃程度 $y$ 的食物需要花费 $x\times y$ 秒。 整个队伍的成绩是 $N$ 名队员吃完食物花费时间的最大值。
比赛前,高桥君的队伍会进行修行。一次修行可以将一名消化代价大于 $0$ 的队员的消化代价减少 $1$。由于修行需要消耗庞大的食费,因此最多只能进行 $K$ 次修行。
通过修行和适当选择每位队员吃的食物,高桥队在比赛中能够获得的最好成绩是多少?
【输入格式】
第 $1$ 行,两个正整数 $N,K$。
第 $2$ 行,$N$ 个正整数 $A_1,A_2,\cdots,A_N$。
第 $3$ 行,$N$ 个正整数 $F_1,F_2,\cdots,F_N$。
【输出格式】
输出高桥队的最好成绩。
【样例 \#1 说明】
$1$ 号队员进行 $4$ 次修行,吃 $2$ 号食物,花费 $0$ 秒。
$2$ 号队员进行 $1$ 次修行,吃 $3$ 号食物,花费 $1$ 秒。
$3$ 号队员进行 $0$ 次修行,吃 $1$ 号食物,花费 $2$ 秒。
总成绩取最大值 $2$ 秒。
【数据说明】
$1 \le N \le 2\times 10^5$
$0 \le K \le 10^{18}$
$1 \le A_i \le 10^6$
$1 \le F_i \le 10^6$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc144/tasks/abc144_e
高橋君は早食い大会に出ることにしました。この大会は $ N $ 人でのチーム戦であり、高橋君のチームは年齢順に $ 1 $ から $ N $ までの番号がついた $ N $ 人のメンバーからなります。メンバー $ i $ の *消化コスト* は $ A_i $ です。
大会では $ 1 $ から $ N $ までの番号がついた $ N $ 個の食べ物が用意されており、食べ物 $ i $ の *食べにくさ* は $ F_i $ です。大会のルールは以下の通りです。
- $ 1 $ 個の食べ物につき $ 1 $ 人のチームメンバーを割り当てる。同じメンバーを複数の食べ物に割り当てることはできない。
- あるメンバーについて、そのメンバーの消化コストが $ x $、担当する食べ物の食べにくさが $ y $ のとき、その食べ物の完食には $ x\ \times\ y $ 秒かかる。
- $ N $ 人のメンバーそれぞれが完食にかかる時間のうち最大値が、チーム全体の成績となる。
コンテストの前に、高橋君のチームは修行をすることにしました。各メンバーは、自分の消化コストが $ 0 $ より小さくならない限り、$ 1 $ 回修行するごとに自分の消化コストを $ 1 $ 減らすことができます。ただし、修行には膨大な食費がかかるため、$ N $ 人合計で $ K $ 回までしか修行することができません。
各メンバーの修行回数と担当する食べ物を適切に選んだとき、チーム全体の成績は最小でいくらになるでしょうか。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられます。
> $ N $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ F_1 $ $ F_2 $ $ ... $ $ F_N $
输出格式
チーム全体の成績の最小値を出力してください。
输入输出样例
输入样例 #1
3 5
4 2 1
2 3 1
输出样例 #1
2
输入样例 #2
3 8
4 2 1
2 3 1
输出样例 #2
0
输入样例 #3
11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2
输出样例 #3
12
说明
### 制約
- 入力はすべて整数
- $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
- $ 0\ \leq\ K\ \leq\ 10^{18} $
- $ 1\ \leq\ A_i\ \leq\ 10^6\ (1\ \leq\ i\ \leq\ N) $
- $ 1\ \leq\ F_i\ \leq\ 10^6\ (1\ \leq\ i\ \leq\ N) $
### Sample Explanation 1
下のようにすることで、チーム全体の成績は $ 2 $ になります。 - メンバー $ 1 $ に $ 4 $ 回修行させ、食べ物 $ 2 $ を割り当てます。完食にかかる時間は $ (4-4)\ \times\ 3\ =\ 0 $ 秒です。 - メンバー $ 2 $ に $ 1 $ 回修行させ、食べ物 $ 3 $ を割り当てます。完食にかかる時間は $ (2-1)\ \times\ 1\ =\ 1 $ 秒です。 - メンバー $ 3 $ に $ 0 $ 回修行させ、食べ物 $ 1 $ を割り当てます。完食にかかる時間は $ (1-0)\ \times\ 2\ =\ 2 $ 秒です。 チーム全体の成績を $ 2 $ より小さくすることはできないので、答えは $ 2 $ です。
### Sample Explanation 2
必ずしも $ K $ 回ちょうど修行する必要はありません。