1499 . 小 Y 與小 P 的藥水調配問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

ytp ytp2026 ytp-junior

Description

小 Y 正在鑽研鍊金術，想要調配出一瓶強力的藥水。她的朋友小 P 提供了 $N$ 種材料，其中第 $i$ 種材料具有三個屬性 $s_i, h_i, p_i$：

  • $s_i$：屬性差，可能為正、負或零。
  • $h_i$：藥效。
  • $p_i$：能量。

小 Y 要從這 $N$ 種材料中選出一個（可能為空的）子集合來調配藥水，所選的材料必須同時滿足以下三個條件：

  • 所選材料的屬性差總和必須恰好為 $0$，否則藥水會變得不穩定。
  • 所選材料的藥效總和至少為 $H$，否則藥水起不了作用。
  • 所選材料的能量總和至多為 $t$，因為小 Y 的鍊金鍋爐一次最多只能承受 $t$ 單位的能量。

在滿足以上三個條件的前提下，藥水的威力和所使用的能量總和成正比，因此小 Y 希望所選材料的能量總和越大越好。請幫小 Y 求出，在所有合法的選法中，能量總和最大可以是多少；如果不存在合法的選法，請輸出 $-1$。

Input Format

輸入第一行有三個正整數 $N, t, H$，代表材料的數量、鍊金鍋爐一次最多能承受的能量，以及藥效總和至少要達到的門檻。

接下來 $N$ 行，第 $i$ 行有三個整數 $s_i, h_i, p_i$，代表第 $i$ 種材料的屬性差、藥效與能量。

  • $1 \leq N \leq 40$
  • $1 \leq t \leq 10^ 9$
  • $1 \leq H \leq 10^ 9$
  • $-10^ 9 \leq s_i \leq 10^ 9$
  • $1 \leq h_i \leq 10^ 9$
  • $1 \leq p_i \leq 10^ 9$

Output Format

輸出一行一個整數，代表在滿足所有限制的前提下，能量總和的最大值；若不存在合法的選法，輸出 -1。

Sample Input 1

4 9 5
2 3 5
-2 2 4
1 1 1
-1 4 6

Sample Output 1

9

Sample Input 2

3 100 1
5 1 1
3 1 1
2 1 1

Sample Output 2

-1

Hints

範測 1 解釋：

選擇第 $1$ 種與第 $2$ 種材料，屬性差總和為 $2 + (-2) = 0$，藥效總和為 $3 + 2 = 5 \geq H = 5$，能量總和為 $5 + 4 = 9 \leq t = 9$，恰好用滿鍋爐的容量。可以證明這是能量總和最大的合法選法。

範測 2 解釋：

三種材料的屬性差分別為 $5, 3, 2$，任何非空子集合的屬性差總和都不可能是 $0$；而選擇空集合的話，藥效總和為 $0$，小於 $H = 1$。因此不存在合法的選法，輸出 $-1$。

Problem Source

2026 YTP 國中組決賽 p11

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測試資料 0
2 2~28 $N \leq 20$ 4
3 29~45 $s_i = 0$ 4
4 46~67 $H = 1$ 4
5 0~107 無額外限制 13

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 5
1 4000 262144 65536 1 5
2 4000 262144 65536 2 5
3 4000 262144 65536 2 5
4 4000 262144 65536 2 5
5 4000 262144 65536 2 5
6 4000 262144 65536 2 5
7 4000 262144 65536 2 5
8 4000 262144 65536 2 5
9 4000 262144 65536 2 5
10 4000 262144 65536 2 5
11 4000 262144 65536 2 5
12 4000 262144 65536 2 5
13 4000 262144 65536 2 5
14 4000 262144 65536 2 5
15 4000 262144 65536 2 5
16 4000 262144 65536 2 5
17 4000 262144 65536 2 5
18 4000 262144 65536 2 5
19 4000 262144 65536 2 5
20 4000 262144 65536 2 5
21 4000 262144 65536 2 5
22 4000 262144 65536 2 5
23 4000 262144 65536 2 5
24 4000 262144 65536 2 5
25 4000 262144 65536 2 5
26 4000 262144 65536 2 5
27 4000 262144 65536 2 5
28 4000 262144 65536 2 5
29 4000 262144 65536 3 5
30 4000 262144 65536 3 5
31 4000 262144 65536 3 5
32 4000 262144 65536 3 5
33 4000 262144 65536 3 5
34 4000 262144 65536 3 5
35 4000 262144 65536 3 5
36 4000 262144 65536 3 5
37 4000 262144 65536 3 5
38 4000 262144 65536 3 5
39 4000 262144 65536 3 5
40 4000 262144 65536 3 5
41 4000 262144 65536 3 5
42 4000 262144 65536 3 5
43 4000 262144 65536 3 5
44 4000 262144 65536 3 5
45 4000 262144 65536 3 5
46 4000 262144 65536 4 5
47 4000 262144 65536 4 5
48 4000 262144 65536 4 5
49 4000 262144 65536 4 5
50 4000 262144 65536 4 5
51 4000 262144 65536 4 5
52 4000 262144 65536 4 5
53 4000 262144 65536 4 5
54 4000 262144 65536 4 5
55 4000 262144 65536 4 5
56 4000 262144 65536 4 5
57 4000 262144 65536 4 5
58 4000 262144 65536 4 5
59 4000 262144 65536 4 5
60 4000 262144 65536 4 5
61 4000 262144 65536 4 5
62 4000 262144 65536 4 5
63 4000 262144 65536 4 5
64 4000 262144 65536 4 5
65 4000 262144 65536 4 5
66 4000 262144 65536 4 5
67 4000 262144 65536 4 5
68 4000 262144 65536 5
69 4000 262144 65536 5
70 4000 262144 65536 5
71 4000 262144 65536 5
72 4000 262144 65536 5
73 4000 262144 65536 5
74 4000 262144 65536 5
75 4000 262144 65536 5
76 4000 262144 65536 5
77 4000 262144 65536 5
78 4000 262144 65536 5
79 4000 262144 65536 5
80 4000 262144 65536 5
81 4000 262144 65536 5
82 4000 262144 65536 5
83 4000 262144 65536 5
84 4000 262144 65536 5
85 4000 262144 65536 5
86 4000 262144 65536 5
87 4000 262144 65536 5
88 4000 262144 65536 5
89 4000 262144 65536 5
90 4000 262144 65536 5
91 4000 262144 65536 5
92 4000 262144 65536 5
93 4000 262144 65536 5
94 4000 262144 65536 5
95 4000 262144 65536 5
96 4000 262144 65536 5
97 4000 262144 65536 5
98 4000 262144 65536 5
99 4000 262144 65536 5
100 4000 262144 65536 5
101 4000 262144 65536 5
102 4000 262144 65536 5
103 4000 262144 65536 5
104 4000 262144 65536 5
105 4000 262144 65536 5
106 4000 262144 65536 5
107 4000 262144 65536 5
Submit
Back to Top