← 返回题目列表

AtCoder · awc0011_e

E. 选择宝箱

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

分数: 466 分

问题陈述

高桥是一名冒险家。探索地牢后他发现 N 宝箱。

的 i第-个宝箱的重量为 A_i 公斤和价值 B_i.

高桥的背包最多可以容纳总重量为 M 公斤。高桥计划从宝箱中选择一定数量的宝箱(可能是零) N 箱子可以放入背包并带回家。然而,由于每个宝箱仅存在一次,因此无法多次选择同一个宝箱。

高桥想要最大化所选宝箱的总价值,但受限于所选宝箱的总重量最多为 M 公斤。使总价值最大化的选择称为 最优选择。可能存在多个最优选择。

对于每个宝箱 i (1 \leq i \leq N),判断是否存在包含宝箱的最优选择 i.

约束

  • 1 \leq N \leq 1,000
  • 1 \leq M \leq 3,000
  • 1 \leq A_i \leq M (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入均为整数

输入

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 第一行包含一个整数 N 代表宝箱数量和一个整数 M 代表背包的容量,以空格分隔。
  • 的 (i + 1)第行 (1 \leq i \leq N) 包含一个整数 A_i 代表重量 i- 第一个宝箱和一个整数 B_i 代表其值,以空格分隔。

输出

打印 N 行。

关于 i第行,打印 Yes 如果存在包含宝箱的最佳选择 i,和 No 否则。


示例输入 1

3 5
2 3
3 4
3 3

示例输出 1

Yes
Yes
No

示例输入 2

4 4
2 5
2 5
2 5
3 1

示例输出 2

Yes
Yes
Yes
No

示例输入 3

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

示例输出 3

Yes
Yes
Yes
No
Yes
No

示例输入 4

10 15
3 10
4 12
5 14
2 7
1 3
6 18
7 20
8 22
3 9
4 11

示例输出 4

Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No

示例输入 5

1 1
1 1

示例输出 5

Yes