← 返回题目列表

AtCoder · ndpc2026_n

N. 背包

中文机器翻译题面 查看原题

分数: 6 点

注意

与其他问题相比,这个问题需要更多的专业知识。
如果您没有完整解决方案的想法,建议先瞄准部分分数,然后继续下一个问题。

问题陈述

每个都有无限多个项目 N 类型。 i第一种类型的物品有重量 i 和值 v_i.

你被给予 Q 查询。在每个查询中,您都会得到一个正整数 W.
当您选择某些物品时,求最大可能的总价值,使得总重量恰好为 W.

约束

  • 1 \leq N \leq 4000
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq v_i \leq 10^9
  • 1 \leq W \leq 10^9
  • 所有输入值均为整数

部分分数

此题得分不全。

  • 如果您使用以下方法求解数据集 N \leq 300,你会得到 4 点。

输入

输入由标准输入给出,格式如下:

N Q
v_1 v_2 \dots v_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均按以下格式给出:

W

输出

打印 Q 行。上 i第行,输出答案 i-第一个查询。


示例输入 1

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

示例输出 1

2
4
7
9
11
14
16
18
21

例如,在第 6 个查询中, W=6.
如果您携带两件以下类型的物品 3,总值变为 7 + 7 = 14,这是最大值。


示例输入 2

10 10
104 231 361 478 661 765 963 1132 1402 1552
1
10
15
27
48
100
853822501
687675302
281611653
844033520

示例输出 2

104
1552
2213
4206
7460
15572
133006571782
107124530332
43868837466
131481666104