分数: 366 分
问题陈述
高桥正在整理家里的书架。书架上有 N 书籍排成一排,编号 1, 2, \ldots, N 从左到右。预订 i 的满意度值为 A_i 和重量 B_i.
高桥想要选择 一本或多本连续的书 将 从书架上移到新书架上。具体来说,他选择整数 l, r (1 \leq l \leq r \leq N)并取出所有书籍 l, l+1, \ldots, r.
但是,高桥一次可以搬运的重量是有限制的,因此所选区间内的书籍总重量必须最多为 K。也就是说,必须满足以下条件:
B_l + B_{l+1} + \cdots + B_r \leq K
在所有选择中 l, r 满足这个条件,找到总满意度的最大值 A_l + A_{l+1} + \cdots + A_r.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数
- 至少存在一个区间 (l, r) (1 \leq l \leq r \leq N) 使得总重量最多为 K
输入
N K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
- 第一行包含一个整数 N 代表书籍数量和一个整数 K 代表重量限制,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每本书的满意度值,以空格分隔。
- 第三行包含整数 B_1, B_2, \ldots, B_N 代表每本书的重量,以空格分隔。
输出
在选择总权重最大的连续区间时,一行打印最大总满意度 K.
示例输入 1
5 10 3 5 2 8 1 4 3 2 5 6
示例输出 1
15
示例输入 2
8 20 1 4 6 2 10 3 7 5 5 3 4 8 6 2 3 9
示例输出 2
25
示例输入 3
10 1000000000000000 100 200 300 400 500 600 700 800 900 1000 1 1 1 1 1 1 1 1 1 1
示例输出 3
5500