| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 11 | 8 | 8 | 80.000% |
Мальчик Витя очень любит слушать музыку. Он пристально следит за обновлениями своих любимых групп, поэтому знает, что в эту пятницу должны быть выпущены $n$ альбомов, $i$-й из которых содержит $k_i$ треков. Разумеется, Витя, как самый преданный фанат, уже послушал все треки, которые должны выйти в ближайшее время, и знает, что в $i$-м альбоме крутость $j$-го трека равна $a_{i,j}$.
У Вити есть подруга Маша, которую он очень хочет пригласить на фестиваль, где выступают его любимые группы. Однако для того, чтобы подруга согласилась, она должна сначала оценить вышедшие новинки. Витя знает, что, если Маша послушает трек, который был круче всех прошлых, она получит 1 единицу впечатления. К сожалению, альбомы можно слушать только целиком, не меняя песни в них местами.
Помогите Вите найти такой порядок альбомов, чтобы впечатление Маши оказалось как можно больше, и она точно сходила вместе с ним на фестиваль.
В первой строке дано единственное целое число $n$ (1ドル \le n \le 200,000円$) --- количество альбомов.
Далее следуют описания альбомов. Каждое описание альбома состоит из двух строк:
В первой строке дано единственное целое число $k_i$ (1ドル \le k_i \le 200,000円$) --- количество треков в $i$-м альбоме.
В следующей строке даны $k_i$ целых чисел $a_{i, 1},\ a_{i, 2},\ a_{i, 3},\ \ldots,\ a_{i, k_i}$ (1ドル \le a_{i,j} \le 200,000円$) --- крутость треков в $i$-м альбоме.
Обозначим за $\sum k_i$ сумму по всем $k_i$. Гарантируется, что $\sum k_i \le 200,000円$.
Выведите единственное число --- максимальное впечатление, которое может может получить Маша.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 14 | $n \le 7,ドル $\sum k_i \le 1000$ |
| 2 | 9 | $a_{i, j} \le 2$ |
| 3 | 12 | $a_{i, j} \le 10$ |
| 4 | 15 | $k_i \le 2$ |
| 5 | 13 | $n \le 1000,ドル $a_{i, j} \le 1000$ |
| 6 | 13 | $n \le 30,000円,ドル $a_{i, j} \le 30,000円$ |
| 7 | 24 |
4 5 4 9 4 6 8 1 7 2 8 6 1 1
4
4 2 3 4 2 1 8 2 2 8 2 7 9
4
В первом тестовом примере оптимальным порядком является прослушивание 4-го, 2-го, 3-го и 1-го альбомов. В таком случае Маша послушает треки в следующем порядке: 1; 7; 8, 6; 4, 9, 4, 6, 8 и получит 4 единицы впечатления.
Во втором тестовом примере необходимо сначала прослушать 1-й, потом 4-й и в любом порядке 2-й и 3-й. В таком случае Маша получит максимальное впечатление, причём за каждую песню в 1-м и 4-м альбомах и ничего за 2-й и 3-й.
Olympiad > Moscow Open Olympiad in Informatics > Moscow Open Olympiad in Informatics 2022-23 > Day 1 DOOM번