Shipping Center

题目描述

我们有 $N$ 件行李，称为 行李 $1$ 到 行李 $N$，以及 $M$ 个箱子，称为 箱子 $1$ 到 箱子 $M$。 行李 $i$ 的大小为 $W_i$，价值为 $V_i$。 箱子 $i$ 可以容纳大小至多为 $X_i$ 的一件行李。它不能容纳两件或更多行李。 你将得到 $Q$ 个查询。在每个查询中，给定两个整数 $L$ 和 $R$，求解如下问题：

问题：在 $M$ 个箱子中，编号为 Box $L,L+1,\ldots,R$ 的 $R-L+1$ 个箱子变为不可用。 找出我们可以同时放入其余箱子中的一组行李的总价值的最大可能值。

输入格式

输入由标准输入按以下格式提供： $N$ $M$ $Q$ $W_1$ $V_1$ $\vdots$ $W_N$ $V_N$ $X_1$ $\ldots$ $X_M$ $\mathrm{Query}_1$ $\vdots$ $\mathrm{Query}_Q$

每个 Query 的格式如下： $L$ $R$

输出格式

输出 $Q$ 行。 第 $i$ 行应包含 $\mathrm{Query}_i$ 所描述问题的答案。

3 4 3
1 9
5 3
7 8
1 8 6 9
4 4
1 4
1 3

20
0
9

提示

$1 \leq N \leq 50$ $1 \leq M \leq 50$ $1 \leq Q \leq 50$ $1 \leq W_i \leq 10^6$ $1 \leq V_i \leq 10^6$ $1 \leq X_i \leq 10^6$ $1 \leq L \leq R \leq M$ 输入中的所有值均为整数。在第 1 个查询中，仅 箱子 4 不可用。 将 行李 $1$ 放入 箱子 $1$，将 行李 $3$ 放入 箱子 $2$，将 行李 $2$ 放入 箱子 $3$，我们可以把所有行李放入箱子，使放入箱子的行李总价值为 $20$。 在第 2 个查询中，所有箱子都不可用；答案为 $0$。 在第 3 个查询中，仅 箱子 4 可用。通过将 行李 $1$ 放入 箱子 $4$，我们可以使放入箱子的行李总价值为 $9$，这是可能的最大结果。

标签: AtCoder|abc195D

来源

AtCoder|abc195D