| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 487 | 117 | 94 | 31.333% |
$1$부터 $N$까지의 번호가 붙어있는 $N$개의 배식대가 있다. $i$번 배식대에서는 $i$번 음식을 배식받을 수 있다. $M$명의 학생들이 음식을 받기 위해 줄을 섰다.
각 학생은 특정 음식을 배식받을 수 있고, 배식받은 음식에 해당하는 만큼 행복도가 상승한다. 구체적인 규칙은 다음과 같다.
초기에 모든 학생의 행복도는 $0$이다. 학생들의 행복도 합이 최대가 되도록 배식을 진행해 보자!
첫 번째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(1\leq N,M\leq10^5)$
이후 각 학생이 먹을 수 있는 음식에 대한 정보가 $M$개의 줄에 걸쳐 주어진다.
정보의 $j$번째 줄에는 $j$번 학생이 먹을 수 있는 음식의 개수를 나타내는 정수 $l_j$가 가장 먼저 주어지고, 이후 $2l_j$개의 정수 $p_{j,1},\,v_{j,1},\,p_{j,2},\,v_{j,2},\,\cdots,\,p_{j,l_j},\,v_{j,l_j}$가 공백으로 구분되어 주어진다. 이때 $p_{j,k}$는 증가하는 순서로 주어진다. $(1\leq j\leq M;$ $1\leq l_j\leq N;$ $1\leq p_{j,1}<p_{j,2}<\cdots<p_{j,l_j}\leq N;$ $1\leq v_{j,k}\leq10^9)$
모든 $l_j$의 합은 $10^5$을 넘지 않는다.
학생들의 행복도 합의 최댓값을 출력한다.
5 5 2 1 5 2 6 1 2 5 1 3 5 1 4 5 1 5 5
26
$1$번 학생이 $1$, $2$번 음식을 배식받고, $3$, $4$, $5$번 학생이 각각 $3$, $4$, $5$번 음식을 배식받으면, 학생들의 행복도의 합은 $(5 + 6) + 0 + 5 + 5 + 5 = 26$이 된다. 이 방법보다 행복도의 합을 크게 할 수 있는 방법은 없으므로, 답은 $26$이 된다.
School > 한국디지털미디어고등학교 > 제 1회 2024 디미고 프로그래밍 챌린지 D번