P13530 [OOI 2023] Music Festival / 音乐节

CF1801C

小男孩维佳非常喜欢听音乐。他一直关注着自己喜欢的乐队，因此知道本周五将有 $n$ 张新专辑发布，第 $i$ 张专辑包含 $k_i$ 首曲目。当然，作为最忠实的粉丝，维佳已经提前听过了所有即将发布的新歌，并且知道第 $i$ 张专辑中第 $j$ 首歌的“酷炫度”为 $a_{i,j}$。 维佳有一个朋友玛莎，他非常希望邀请玛莎一起去参加有他最喜欢乐队出演的音乐节。不过要想让玛莎答应，玛莎需要先体验一下这些新歌。维佳知道，如果玛莎听到的某首歌酷炫度超过她此前听过的所有歌，她就会获得 $1$ 点“印象值”。遗憾的是，专辑只能整张播放，且专辑内歌曲顺序不能改变。 请帮助维佳安排专辑的播放顺序，使得玛莎获得的印象值尽可能大，这样她一定会答应和他一起去音乐节。

第一行包含一个整数 $n$（$1 \le n \le 200\,000$），表示专辑数量。 接下来是 $n$ 组专辑描述。每组描述包含两行： - 第一行包含一个整数 $k_i$（$1 \le k_i \le 200\,000$），表示第 $i$ 张专辑的曲目数。 - 第二行包含 $k_i$ 个整数 $a_{i, 1},\ a_{i, 2},\ \ldots,\ a_{i, k_i}$（$1 \le a_{i,j} \le 200\,000$），依次表示第 $i$ 张专辑每首歌的酷炫度。 记 $\sum k_i$ 为所有专辑曲目数之和。保证 $\sum k_i \le 200\,000$。

输出一个整数，表示玛莎最多能获得的印象值。

### 样例解释 在第一个测试样例中，最优的播放顺序是先听第 $4$ 张、再听第 $2$ 张、第 $3$ 张和第 $1$ 张专辑。这样玛莎依次听到的歌曲为：**1**；**7**；**8**, 6；4, **9**, 4, 6, 8。玛莎将获得 $4$ 点印象值。 在第二个测试样例中，应先播放第 $1$ 张专辑，再播放第 $4$ 张，之后第 $2$ 和第 $3$ 张顺序任意。这样玛莎能获得最大印象值，且第 $1$ 和第 $4$ 张专辑的每首歌都能带来印象值，第 $2$ 和第 $3$ 张专辑则不会带来新的印象值。 ### 评分说明 本题测试点分为 7 组。只有通过某一组所有测试点，且通过部分之前组所有测试点，才能获得该组分数。有些分组不要求通过样例测试点。 | 组别 | 分值 | $n$ | $k_i$ | $a_{i, j}$ | 必须通过的组 | 备注 | |:----:|:----:|:---:|:-----:|:----------:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | 样例测试点 | | 1 | 14 | $n \le 7$ | $\sum k_i \le 1000$ | -- | 0 | | | 2 | 9 | -- | -- | $a_{i, j} \le 2$ | -- | | | 3 | 12 | -- | -- | $a_{i, j} \le 10$ | 0, 2 | | | 4 | 15 | -- | $k_i \le 2$ | -- | -- | | | 5 | 13 | $n \le 1000$ | -- | $a_{i, j} \le 1000$ | 0 | | | 6 | 13 | $n \le 30\,000$ | -- | $a_{i, j} \le 30\,000$ | 0, 5 | | | 7 | 24 | -- | -- | -- | 0--6 | |