赛博粒子 (cyber)
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
本题需要使用文件重定向,输入输出文件名cyber.in/cyber.out
题目描述
在 2077 年,由于地球资源即将枯竭,能源危机也即将爆发。而在此时,人类发现了一种新的物质:赛博粒子。这种粒子通常具有非常大的能量,而如果人类能够很好地利用这种粒子所蕴含的能量,那么就可以很好地避免这场能源危机的爆发。于是,众多科学家对其展开了研究。
这种粒子的能量并不是一成不变的,并且并非所有赛博粒子的能量变换都相同。于是,科学家收集了 种不同的赛博粒子,每一种赛博粒子仅有一个。对于第 种粒子来说,刚开始收集到的时候的能量为 ,而其每经过 秒,能量就会变成 ,注意能量可能减到负数。
为了使得能量可控,科学家们发明了一种机器,可以固定赛博粒子的能量。另外,机器固定每一个粒子所需要的时间是不同的。固定一个第 种的粒子需要的时间为 秒。另外,这个固定粒子能量的机器有一个限制:同一时刻只能固定一个粒子,并且一旦开始固定,这个过程就必须等到固定完成才能继续下一次固定工作。
科学家们想研究如下问题:给定时间限制 秒,在这 秒之内能够固定下来的粒子的能量之和最大可以是多少?由于科学家们没学过算法,所以他们来找你寻求帮助。
输入格式
第一行输入两个正整数 ,表示收集到的粒子种类数和时间限制。
接下来 行,每行输入三个非负整数 ,含义见题面。
输出格式
输出一行一个整数,表示能够固定下来的粒子的能量之和的最大值。
样例
3 10
15 2 3
11 1 7
18 3 1
22
样例解释 1
先固定第 三 个粒子,固定需要 1 秒,固定后能量为 15,此时第一个粒子的能量为 13,第二个粒子的能量为 10;
之后如果固定第一个粒子,则需要 3 秒,固定后的能量为 ,固定的粒子能量一共为 22;
如果固定第二个粒子,则需要 7 秒,固定后的能量为 ,固定的粒子能量一共为 18。
故答案为 22。
10 100
1405 1120 2
81030 1066 4
2327 1996 7
73870 1450 1
61478 1705 6
62949 1572 5
99179 1355 5
49322 1709 2
75088 1246 6
5893 1408 2
373496
样例输入 3
见选手下发文件 cyber_sample3.in
样例输出 3
见选手下发文件 cyber_sample3.out
数据范围
本题的各个测试点对应的数据范围如下表所示。
测试点编号 | 特殊范围 | ||
---|---|---|---|
1 | 无 | ||
2 | |||
3 | |||
4 | |||
5 | |||
6 | |||
7 | |||
8 | |||
9 | $=$1 | ||
10 | |||
11 | |||
12 | |||
13 | |||
14 | |||
15 | 无 | ||
16 | |||
17 | |||
18 | |||
19 | |||
20 |
对于 100% 的数据,$1\le n \le 50, 1\le C,c_i \le 10^5, 0 \le a_i,b_i\le 10^5$
来源
by Vingying
C2024届二阶(下)测试题(20230723)
- 状态
- 已结束
- 规则
- OI
- 题目
- 4
- 开始于
- 2023-7-22 18:30
- 结束于
- 2023-7-22 22:00
- 持续时间
- 3.5 小时
- 主持人
- 参赛人数
- 27