2199 . 大促銷改（Discount）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

22.4% (17/76)

Tags

Description

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

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

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

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

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

Input Format

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

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

接下來 M 行，第 i 行第一個數字 di 代表第 i 個優惠組合的價格，第二個數字 ki 代表這個優惠組合含有幾種商品，接下來會有 ki 個正整數 cij，代表這個優惠組合含有 cij 號商品。

Output Format

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

Sample Input 1

5 2 7
1 2 5 3 4
6 2 2 3
5 3 1 4 5

Sample Output 1

4

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 2

6

Hints

測資限制：

  • 1≤N≤3000。
  • 0≤M。
  • 1≤ki,cij≤N。
  • 1≤pi,di,X≤109。
  • 若把所有優惠組合當成 M 個點，在會衝突的優惠組合對之間建邊的話，將不會存在任何環。

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

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

Problem Source

2021 板中TOI模考模擬賽

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Back to Top