P11430 [COCI 2024/2025 #2] 游戏 / Igre

题目背景

译自 COCI 2024/2025 #2 T2。$\texttt{2s,0.5G}$。满分为 $70$。

题目描述

游戏 $i$ 需要 $p_i$ 分钟来学习。一款游戏只有学习怎么玩之后才可以玩。

玩一局游戏 $i$ 需要 $t_i$ 分钟，可以获得 $o_i$ 分。可以多次游玩一款游戏。

适度游戏益脑，过度游戏伤身。如果只花 $m$ 分钟来玩（包括学习玩）游戏，最多可以获得多少分？

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，每行三个整数 $p_i,t_i,o_i$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3 10
2 3 5
5 1 5
3 2 5

输出 #1

25

输入输出样例 #2

输入 #2

4 13
0 6 5
0 3 4
0 2 3
0 4 4

输出 #2

19

输入输出样例 #3

输入 #3

3 10
1 1 1
3 2 3
2 3 5

输出 #3

11

说明/提示

样例解释

样例 $3$ 解释：

学第 $1,3$ 款游戏，耗时 $1+2=3$ 分钟。

游玩游戏 $1,3,3$，获得 $1+5+5=11$ 分，耗时 $1+3+3=7$ 分钟。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n,m,t_i\le 5\, 000$；
• $0\le p_i\le 5\, 000$；
• $1\le o_i\le 10^9$。

子任务编号	$n\le$	特殊性质	得分
$1$	$1$		$6$
$2$	$10$		$13$
$3$	$5\, 000$	A	$23$
$4$			$28$

• 特殊性质 A：$\forall 1\le i\le n$，$p_i=0$。

• #5699. 「COCI 2024/2025 #2」Igre

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #2 T2「Igre」

Kile 从棋盘游戏展上回来了。他带回家 $n$ 个游戏。在玩游戏之前，有必要先学习其规则。学习第 $i$ 个游戏的规则需要 $p_{i}$ 分钟。一旦规则学会，就可以玩这个游戏了。玩第 $i$ 个游戏需要 $t_{i}$ 分钟。每个游戏还有它自己的评分 $o_{i}$。

在接下来的日子里，Kile 计划在棋盘游戏上花费至多 $d$ 分钟。他想知道他能玩的游戏所获得的评分之和的最大值。每个游戏可以玩任意多次。

输入格式

第一行包含整数 $n$ 和 $d$ $(1 \leq n, d \leq 5000)$，表示游戏的数量和计划玩游戏的时间。

接下来的 $n$ 行中，第 $i$ 行包含整数 $p_{i}, t_{i}$ 和 $o_{i}$ $(0 \leq p_{i} \leq 5000, 1 \leq t_{i} \leq 5000, 1 \leq o_{i} \leq 10^{9})$，分别表示学习规则所需的时间、玩游戏所需的时间以及第 $i$ 个游戏的评分。

输出格式

在第一行输出所玩游戏评分之和的最大值。

样例 1

输入

3 10
2 3 5
5 1 5
3 2 5

输出

25

样例 2

输入

4 13
0 6 5
0 3 4
0 2 3
0 4 4

输出

19

样例 3

输入

3 10
1 1 1
3 2 3
2 3 5

输出

11

实现总分 $11$ 的一种方式如下：在第一分钟，Kile 学习玩第一个游戏，然后玩了一次。在那之后，他花费两分钟学习玩第三个游戏，并在最后 $6$ 分钟里玩了两次。通过这种方式，所玩游戏的总评分为：$1+5+5=11$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$6$	$n=1$
$2$	$13$	$n \leq 10$
$3$	$23$	对于所有的 $i=1, \ldots, n$，都有 $p_{i}=0$
$4$	$28$	无附加限制