AT_abc195_d [ABC195D] Shipping Center

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的行李，以及 $M$ 个编号为 $1$ 到 $M$ 的箱子。

第 $i$ 个行李的大小为 $W_i$，价值为 $V_i$。

第 $i$ 个箱子可以装下大小不超过 $X_i$ 的行李。每个箱子最多只能装一个行李。

有 $Q$ 个查询。每个查询给出两个整数 $L, R$，请你解决以下问题：

• 问题：在 $M$ 个箱子中，编号为 $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$

每个查询的格式如下：

$L$ $R$

输出格式

输出 $Q$ 行。

第 $i$ 行输出第 $\mathrm{Query}_i$ 对应问题的答案。

输入输出样例 #1

输入 #1

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

输出 #1

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

对于第 $1$ 个查询，箱子 $4$ 无法使用。将行李 $1$ 放入箱子 $1$，行李 $3$ 放入箱子 $2$，行李 $2$ 放入箱子 $3$，可以将所有行李都放入箱子，总价值为 $20$。

对于第 $2$ 个查询，所有箱子都无法使用，因此答案为 $0$。

对于第 $3$ 个查询，只有箱子 $4$ 可以使用。将行李 $1$ 放入箱子 $4$，最大总价值为 $9$。

由 ChatGPT 4.1 翻译