QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

#11447. 汤姆的厨房

Statistics

Tom's Kitchen 是一家非常受欢迎的餐厅。它受欢迎的原因之一是每一道菜都由至少 $K$ 位不同的厨师准备。今天,有 $N$ 道菜需要准备,其中第 $i$ 道菜需要 $A_i$ 小时的工时。

Tom 可以雇佣 $M$ 位厨师来准备所有的菜,但第 $j$ 位厨师最多工作 $B_j$ 小时。此外,即使厨师实际工作的时间少于 $B_j$ 小时,他也必须获得 $B_j$ 小时的全额报酬。一位厨师可以参与多道菜的制作,且在每道菜上投入的时间可以不同。只有当至少 $K$ 位厨师参与某道菜的制作,且他们投入的总时间恰好为 $A_i$ 小时时,这道菜才算准备妥当。当一位厨师参与某道菜的制作时,他投入的时间必须是正整数小时。

Tom 需要帮助,以选择最优的厨师子集,使得厨师在未工作但仍获得报酬的时间总和最小。

输入格式

第一行包含整数 $N$、$M$ 和 $K$。

第二行包含 $N$ 个整数 $A_i$,第三行包含 $M$ 个整数 $B_j$。

输出格式

输出一行,包含 Tom 选择最优厨师子集时,厨师未工作但仍获得报酬的时间总和。如果无法按照上述规则准备好所有 $N$ 道菜,则输出 “Impossible”。

样例

样例输入 1

1 2 2
5
3 4

样例输出 1

2

说明:Tom 需要两位厨师来准备这道菜,因此他必须雇佣所有可用的两位厨师。无论他们如何分配工作,最终他们总共工作了 5 小时,但获得了 $3 + 4 = 7$ 小时的报酬,因此多付了 2 小时的报酬。

样例输入 2

1 1 2
5
5

样例输出 2

Impossible

说明:Tom 需要两位厨师来准备这道菜,但只有一位厨师可用。

样例输入 3

3 3 3
3 3 2
3 3 3

样例输出 3

Impossible

说明:第 3 道菜无法由三位厨师准备,因为每位厨师至少需要工作 1 小时,而这道菜只需要 2 小时。

子任务

测试组满足以下条件:

  1. (9 分) $1 \le N, K \le 300, 1 \le M \le 2, 1 \le A_i, B_j \le 300$。
  2. (22 分) $1 \le N, K \le 300, 1 \le M \le 15, 1 \le A_i, B_j \le 300$。
  3. (20 分) $1 \le N, M, A_i, B_j \le 300, K = 1$。
  4. (21 分) $1 \le N, M, K, A_i, B_j \le 40$。
  5. (28 分) $1 \le N, M, K, A_i, B_j \le 300$。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.