2199 . 大促銷改（Discount）

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

19.4% (14/72)

Tags

Description

家豪超市正在舉行一年一度的大特賣，有許多的優惠組合供顧客選購。

每個優惠組合 $S$ 可能含有一個或以上的商品，如果一次購買這些商品的話，可以用優惠價購買，當然也可以選擇用原價一項一項購買。我們說兩種優惠組合 $S_i,S_j$ 產生衝突代表存在一個商品同時被這兩種優惠組合所包含，所謂並用即代表使用了會產生衝突的優惠組合。

超市內有 $N$ 項商品、 $M$ 種優惠組合，你現在有 $X$ 元，你想要盡可能的買多一點種類的商品回家，且同樣的商品只能買一次，請問在最佳的購買策略、以及不使用會衝突的優惠組合的情況下，你最多能購買幾種商品？

當然，這個問題非常的困難，因此我們保證「若把所有優惠組合當成 $M$ 個點，在會衝突的優惠組合對之間建邊的話，將不會存在任何環」。

家豪：沒人說優惠價一定要比較便宜 O $\omega$ O

Input Format

首行輸入三個整數 $N,M,X$，分別代表商品種類、優惠組合數量以及你擁有的錢。

接下來一行有 $N$ 個正整數，第 $i$ 個數字 $p_i$ 代表 $i$ 號物品的價格。

接下來 $M$ 行，第 $i$ 行第一個數字 $d_i$ 代表第 $i$ 個優惠組合的價格，第二個數字 $k_i$ 代表這個優惠組合含有幾種商品，接下來會有 $k_i$ 個正整數 $c_{ij}$，代表這個優惠組合含有 $c_{ij}$ 號商品。

Output Format

請輸出一個整數，代表你最多能買到幾種物品。

Sample Input

Sample Input 1
5 2 7
1 2 5 3 4
6 2 2 3
5 3 1 4 5

Sample Input 2
6 4 17
2 5 7 3 4 3
3 2 1 2
9 2 4 5
10 2 2 3
8 2 3 5

Sample Output

Sample Output 1
4

Sample Output 2
6

Hints

測資限制：

  • $1\le N\le 3000$。
  • $0\le M$。
  • $1\le k_i,c_{ij}\le N$。
  • $1\le p_i,d_i,X\le 10^ 9$。
  • 若把所有優惠組合當成 $M$ 個點，在會衝突的優惠組合對之間建邊的話，將不會存在任何環。

本題共有 $6$ 組測試題組，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

  1. ($14\%$) $N\le 10$，$p_i,d_i,X\le 3000$。
  2. ($17\%$) $p_i,d_i,X\le 3000$，任兩個優惠組合之間皆不衝突。
  3. ($11\%$) 任兩個優惠組合之間皆不衝突。
  4. ($33\%$) $N\le 300$。
  5. ($13\%$) $p_i,d_i,X\le 3000$。
  6. ($12\%$) 無額外限制。

Problem Source

2021 板中TOI模考模擬賽

Subtasks

No. Testdata Range Constraints Score
1 2~26 $N\le 10$，$p_i,d_i,X\le 3000$。 14
2 27~39 $p_i,d_i,X\le 3000$，任兩個優惠組合之間皆不衝突。 17
3 27~52 任兩個優惠組合之間皆不衝突。 11
4 53~68 $N\le 300$。 33
5 2~39, 69~94 $p_i,d_i,X\le 3000$。 13
6 0~119 無額外限制。 12

Testdata and Limits

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