AT_abc390_e.[ABC390E] Vitamin Balance

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 种食物，每种食物恰好含有维生素 $1$ 、 $2$ 、 $3$ 中的一种。
具体来说，吃第 $i$ 种食物时，可以摄取维生素 $V_i$ 的量为 $A_i$ ，同时摄入卡路里 $C_i$ 。

高桥君可以选择吃其中的若干种食物（包括 $0$ 种），使得总摄入卡路里不超过 $X$ 。
请计算在此条件下，「维生素 $1$ 、 $2$ 、 $3$ 中摄入量最少的那种维生素的摄入量」可能达到的最大值。

输入格式

输入从标准输入给出，格式如下：

$N$ $X$
$V_1$ $A_1$ $C_1$
$V_2$ $A_2$ $C_2$
$\vdots$
$V_N$ $A_N$ $C_N$

输出格式

输出在总卡路里不超过 $X$ 的条件下，「维生素 $1$ 、 $2$ 、 $3$ 中摄入量最少的那种维生素的摄入量」的最大可能值。

输入输出样例

输入#1
```
5 25
1 8 5
2 3 5
2 7 10
3 2 5
3 3 10
```
输出#1
```
3
```
输入#2
```
2 5000
1 200000 1
2 200000 1
```
输出#2
```
0
```

说明/提示

约束条件

$1 \leq N \leq 5000$
$1 \leq X \leq 5000$
$1 \leq V_i \leq 3$
$1 \leq A_i \leq 2 \times 10^5$
$1 \leq C_i \leq X$
输入均为整数

样例解释 1

各食物的摄入效果如下：

吃第 $1$ 种食物：摄入维生素 $1$ 的量为 $8$ ，卡路里为 $5$
吃第 $2$ 种食物：摄入维生素 $2$ 的量为 $3$ ，卡路里为 $5$
吃第 $3$ 种食物：摄入维生素 $2$ 的量为 $7$ ，卡路里为 $10$
吃第 $4$ 种食物：摄入维生素 $3$ 的量为 $2$ ，卡路里为 $5$
吃第 $5$ 种食物：摄入维生素 $3$ 的量为 $3$ ，卡路里为 $10$

若选择吃第 $1$ 、 $2$ 、 $4$ 、 $5$ 种食物，总卡路里为 $5+5+5+10=25$ ，维生素摄入量分别为 $8$ （维生素 $1$ ）、 $3$ （维生素 $2$ ）、 $5$ （维生素 $3$ ）。此时最小值是维生素 $2$ 的 $3$ 。
无法在总卡路里 $\leq 25$ 的条件下使三种维生素的摄入量均达到 $4$ 或以上，因此输出 $3$ 。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页