家豪超市正在舉行一年一度的大特賣,有許多的優惠組合供顧客選購。
每個優惠組合 $S$ 可能含有一個或以上的商品,如果一次購買這些商品的話,可以用優惠價購買,當然也可以選擇用原價一項一項購買。我們說兩種優惠組合 $S_i,S_j$ 產生衝突代表存在一個商品同時被這兩種優惠組合所包含,所謂並用即代表使用了會產生衝突的優惠組合。
超市內有 $N$ 項商品、 $M$ 種優惠組合,你現在有 $X$ 元,你想要盡可能的買多一點種類的商品回家,且同樣的商品只能買一次,請問在最佳的購買策略、以及不使用會衝突的優惠組合的情況下,你最多能購買幾種商品?
當然,這個問題非常的困難,因此我們保證「若把所有優惠組合當成 $M$ 個點,在會衝突的優惠組合對之間建邊的話,將不會存在任何環」。
家豪:沒人說優惠價一定要比較便宜 O $\omega$ O
首行輸入三個整數 $N,M,X$,分別代表商品種類、優惠組合數量以及你擁有的錢。
接下來一行有 $N$ 個正整數,第 $i$ 個數字 $p_i$ 代表 $i$ 號物品的價格。
接下來 $M$ 行,第 $i$ 行第一個數字 $d_i$ 代表第 $i$ 個優惠組合的價格,第二個數字 $k_i$ 代表這個優惠組合含有幾種商品,接下來會有 $k_i$ 個正整數 $c_{ij}$,代表這個優惠組合含有 $c_{ij}$ 號商品。
請輸出一個整數,代表你最多能買到幾種物品。
測資限制:
本題共有 $6$ 組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。
2021 板中TOI模考模擬賽
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 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 524288 | 65536 | |
1 | 1000 | 524288 | 65536 | |
2 | 1000 | 524288 | 65536 | |
3 | 1000 | 524288 | 65536 | |
4 | 1000 | 524288 | 65536 | |
5 | 1000 | 524288 | 65536 | |
6 | 1000 | 524288 | 65536 | |
7 | 1000 | 524288 | 65536 | |
8 | 1000 | 524288 | 65536 | |
9 | 1000 | 524288 | 65536 | |
10 | 1000 | 524288 | 65536 | |
11 | 1000 | 524288 | 65536 | |
12 | 1000 | 524288 | 65536 | |
13 | 1000 | 524288 | 65536 | |
14 | 1000 | 524288 | 65536 | |
15 | 1000 | 524288 | 65536 | |
16 | 1000 | 524288 | 65536 | |
17 | 1000 | 524288 | 65536 | |
18 | 1000 | 524288 | 65536 | |
19 | 1000 | 524288 | 65536 | |
20 | 1000 | 524288 | 65536 | |
21 | 1000 | 524288 | 65536 | |
22 | 1000 | 524288 | 65536 | |
23 | 1000 | 524288 | 65536 | |
24 | 1000 | 524288 | 65536 | |
25 | 1000 | 524288 | 65536 | |
26 | 1000 | 524288 | 65536 | |
27 | 1000 | 524288 | 65536 | |
28 | 1000 | 524288 | 65536 | |
29 | 1000 | 524288 | 65536 | |
30 | 1000 | 524288 | 65536 | |
31 | 1000 | 524288 | 65536 | |
32 | 1000 | 524288 | 65536 | |
33 | 1000 | 524288 | 65536 | |
34 | 1000 | 524288 | 65536 | |
35 | 1000 | 524288 | 65536 | |
36 | 1000 | 524288 | 65536 | |
37 | 1000 | 524288 | 65536 | |
38 | 1000 | 524288 | 65536 | |
39 | 1000 | 524288 | 65536 | |
40 | 1000 | 524288 | 65536 | |
41 | 1000 | 524288 | 65536 | |
42 | 1000 | 524288 | 65536 | |
43 | 1000 | 524288 | 65536 | |
44 | 1000 | 524288 | 65536 | |
45 | 1000 | 524288 | 65536 | |
46 | 1000 | 524288 | 65536 | |
47 | 1000 | 524288 | 65536 | |
48 | 1000 | 524288 | 65536 | |
49 | 1000 | 524288 | 65536 | |
50 | 1000 | 524288 | 65536 | |
51 | 1000 | 524288 | 65536 | |
52 | 1000 | 524288 | 65536 | |
53 | 1000 | 524288 | 65536 | |
54 | 1000 | 524288 | 65536 | |
55 | 1000 | 524288 | 65536 | |
56 | 1000 | 524288 | 65536 | |
57 | 1000 | 524288 | 65536 | |
58 | 1000 | 524288 | 65536 | |
59 | 1000 | 524288 | 65536 | |
60 | 1000 | 524288 | 65536 | |
61 | 1000 | 524288 | 65536 | |
62 | 1000 | 524288 | 65536 | |
63 | 1000 | 524288 | 65536 | |
64 | 1000 | 524288 | 65536 | |
65 | 1000 | 524288 | 65536 | |
66 | 1000 | 524288 | 65536 | |
67 | 1000 | 524288 | 65536 | |
68 | 1000 | 524288 | 65536 | |
69 | 1000 | 524288 | 65536 | |
70 | 1000 | 524288 | 65536 | |
71 | 1000 | 524288 | 65536 | |
72 | 1000 | 524288 | 65536 | |
73 | 1000 | 524288 | 65536 | |
74 | 1000 | 524288 | 65536 | |
75 | 1000 | 524288 | 65536 | |
76 | 1000 | 524288 | 65536 | |
77 | 1000 | 524288 | 65536 | |
78 | 1000 | 524288 | 65536 | |
79 | 1000 | 524288 | 65536 | |
80 | 1000 | 524288 | 65536 | |
81 | 1000 | 524288 | 65536 | |
82 | 1000 | 524288 | 65536 | |
83 | 1000 | 524288 | 65536 | |
84 | 1000 | 524288 | 65536 | |
85 | 1000 | 524288 | 65536 | |
86 | 1000 | 524288 | 65536 | |
87 | 1000 | 524288 | 65536 | |
88 | 1000 | 524288 | 65536 | |
89 | 1000 | 524288 | 65536 | |
90 | 1000 | 524288 | 65536 | |
91 | 1000 | 524288 | 65536 | |
92 | 1000 | 524288 | 65536 | |
93 | 1000 | 524288 | 65536 | |
94 | 1000 | 524288 | 65536 | |
95 | 1000 | 524288 | 65536 | |
96 | 1000 | 524288 | 65536 | |
97 | 1000 | 524288 | 65536 | |
98 | 1000 | 524288 | 65536 | |
99 | 1000 | 524288 | 65536 | |
100 | 1000 | 524288 | 65536 | |
101 | 1000 | 524288 | 65536 | |
102 | 1000 | 524288 | 65536 | |
103 | 1000 | 524288 | 65536 | |
104 | 1000 | 524288 | 65536 | |
105 | 1000 | 524288 | 65536 | |
106 | 1000 | 524288 | 65536 | |
107 | 1000 | 524288 | 65536 | |
108 | 1000 | 524288 | 65536 | |
109 | 1000 | 524288 | 65536 | |
110 | 1000 | 524288 | 65536 | |
111 | 1000 | 524288 | 65536 | |
112 | 1000 | 524288 | 65536 | |
113 | 1000 | 524288 | 65536 | |
114 | 1000 | 524288 | 65536 | |
115 | 1000 | 524288 | 65536 | |
116 | 1000 | 524288 | 65536 | |
117 | 1000 | 524288 | 65536 | |
118 | 1000 | 524288 | 65536 | |
119 | 1000 | 524288 | 65536 |