首页 > 试题广场 >

我有一个博丽灵梦

[编程题]我有一个博丽灵梦
  • 热度指数：153 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}笨蛋同学打算在接下来的 n 天学习。她有一个“压力值”，初始压力值为 0。
\hspace{15pt}第 i 天，你需要在下面两种行为中选择一种（只能选一种）：
\hspace{23pt}\bullet\,学习：获得 a_i 点知识，压力值增加 b_i；
\hspace{23pt}\bullet\,做博丽灵梦：不获得知识，压力值减少 b_i。如果减少后压力值变成负数，则压力值视为 0。
\hspace{15pt}要求在每一天做出选择后，压力值都不超过 m（即压力值始终满足 0 \leqq 压力值 \leqq m）。
\hspace{15pt}请你计算：在最优的安排下，经过这 n 天后，最多能获得多少知识。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 2 \times 10^5\right) 代表数据组数，每组测试数据描述如下：
\hspace{15pt}第一行输入两个整数 n,m \left(1 \leqq n, m \leqq 3 \times 10^3\right)，表示天数与压力上限。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 10^9\right)，表示第 i 天学习能获得的知识。
\hspace{15pt}第三行输入 n 个整数 b_1, b_2, \dots, b_n \left(1 \leqq b_i \leqq 3 \times 10^3\right)，表示第 i 天压力变化的数值。
\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 6 \times 10^3，m 之和不超过 6 \times 10^3。


输出描述:
\hspace{15pt}对于每一组测试数据，新起一行。输出笨蛋同学最多能获得多少知识。
示例1

输入

2
3 5
4 2 7
3 4 2
4 3
5 5 5 5
4 1 2 3

输出

11
10

说明

\hspace{23pt}\bullet\,对于第 1 组数据：一种获得最多知识的安排是第 1 天学习（压力从 0 变为 3，知识 +4），第 2 天做博丽灵梦（压力从 3 变为 0），第 3 天学习（压力从 0 变为 2，知识 +7），总知识为 11；
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 15浏览

热门推荐

相关试题

我有一个博丽灵梦

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号