P9589 - Donkey Thinks...

内存限制：1024 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：3 通过：1

Donkey thinks potato chips are the best food ever!

So today, when he decides to go on a long journey, he wants his backpack filled with all kinds of potato chips. He searches through the snack zone in his home and finds lots of potato chips.

To better decide which bags of potato chips to bring with him (a subset of the total bags, possibly none of them), he defines the property of a bag of chips as follows:

$h_{i}$ . The happiness this bag of chips can give to Donkey.

$s_{i}$ . The space this bag of chips occupies.

$d_{i}$ . The delicacy of this bag of chips.

For simplicity, we note

h_{i}, s_{i}, d_{i}

as the "happiness", "space" and "delicacy" of the bag.

The total occupied space of the chosen bags can't exceed the volume of the backpack, which is

V

However, the unoccupied space may cause bumps when Donkey moves during the journey, which further causes value loss. If the chosen chips are

i_{1}, i_{2}, \dots, i_{k} (k \geq 1)

and the unoccupied space is

U

, the total value loss on account of bumps is

(d_{i_{1}} + d_{i_{2}} + \dots + d_{i_{k}}) \times U

. If you choose no bag of chips, the value loss is

0

Considering both the advantages and disadvantages of bringing chips, the value of the whole backpack is the sum of happiness brought by these bags of chips minus the value loss. Donkey wants to maximize this value, but just can't make the decision. Help is needed for this!

Each test contains multiple test cases. The first line contains the number of test cases

T (1 \leq T \leq 1 0^{4})

.
Each test case consists of many lines.
The first line contains

2

integers

n, V (1 \leq n \leq 1 0^{5}, 1 \leq V \leq 500)

, the number of chip bags and the total volume of the bag.
Each line from the

2

-nd to the

(n + 1)

-th contains

3

integers

h_{i}, s_{i}, d_{i} (1 \leq s_{i} \leq 500, 1 \leq h_{i}, d_{i} \leq 1 0^{9})

, the "happiness", "space" and "delicacy" of the

i

-th bag of chips.
It is guaranteed that

\sum n

over all test cases in one test will not exceed

1 0^{5}

, and

\sum V^{2}

over all test cases in one test will not exceed

2.5 \times 1 0^{5}

For each test case, output one integer: the maximum value.

7
12

In the first case, Donkey only chooses the first bag, resulting in a value of

10 - (5 - 2) \times 1 = 7

.
In the second case, Donkey chooses both the first bag and the second bag, resulting in a value of

10 + 2 - (5 - 2 - 3) \times (1 + 101) = 12

.
It can be proved that there are no better strategies.

2025暑期牛客赛2

9589: Donkey Thinks...

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签