(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
잇창명은 걸그룹 여자친구의 팬이다. 잇창명은 여자친구 관련 소식을 꼼꼼히 챙기고 있기 때문에 지금까지 n개의 앨범을 발매했고 그 중 i집에는 ki곡이 수록되어 있다는 것을 모두 기억하고 있다. 잇창명은 여자친구의 신곡을 그 누구보다 빠르게 들어보기 때문에 i집의 j번 트랙은 ai,j만큼 멋지다는 것을 당연히 알고 있다.
잇창명은 박한별을 여자친구 콘서트에 초대하고 싶어 한다. 박한별은 아직 여자친구의 곡을 들어본 적이 없기 때문에 먼저 앨범을 들어보고 괜찮은지 평가해 보아야 한다. 박한별은 앨범의 수록곡을 항상 수록된 순서대로만 들으며, 이전에 들은 어떤 여자친구 곡보다도 더 멋진 곡을 들을 때마다 1의 감동을 받는다.
잇창명은 박한별과 함께 콘서트에 가기 위해 박한별의 감동 수치를 최대화하고자 한다. 박한별에게 추천할 앨범 순서를 찾는 프로그램을 작성하여라.
입력
첫째 줄에 여자친구가 발매한 앨범의 수 n이 주어진다. (1 ≤ n ≤ 200,000)
둘째 줄부터 각 앨범의 정보가 순서대로 주어진다. 각 앨범의 정보는 두 줄에 걸쳐 주어지며, 그 중 i집에 대해 첫째 줄에는 수록된 곡의 수 ki, 둘째 줄에는 수록곡의 멋짐 수치 ai,1, ai,2, ..., ai,k_i가 공백으로 구분되어 주어진다. (1 ≤ ki ≤ 200,000, 1 ≤ ai,j ≤ 200,000)
모든 앨범의 수록곡 수의 합 Σki는 200,000곡 이하이다.
출력
박한별이 받을 수 있는 최대 감동 수치를 한 줄로 출력한다.
서브태스크
번호
배점
제한
1
14
n ≤ 7, Σki ≤ 1,000
2
9
ai,j ≤ 2
3
12
ai,j ≤ 10
4
15
ki ≤ 2
5
13
n ≤ 1,000, ai,j ≤ 1,000
6
13
n ≤ 30,000, ai,j ≤ 30,000
7
24
추가 제한 조건이 없다.
노트
예제 입력 1의 경우 4집, 2집, 3집, 1집 순서대로 듣는 것이 최적이다. 이때 박한별이 듣는 곡의 멋짐 수치는 1; 7; 8, 6; 4, 9, 4, 6, 8이 되고 4만큼의 감동을 받는다.
예제 입력 2의 경우 1집과 4집을 순서대로 듣고, 그 다음 2집과 3집은 아무 순서로 들어도 된다. 이때 박한별은 1집과 4집의 모든 곡에서 감동을 받고 2집과 3집에서는 감동을 받지 않는다.
dlaud5379 1년 전 1
(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
잇창명은 걸그룹 여자친구의 팬이다. 잇창명은 여자친구 관련 소식을 꼼꼼히 챙기고 있기 때문에 지금까지 n개의 앨범을 발매했고 그 중 i집에는 ki곡이 수록되어 있다는 것을 모두 기억하고 있다. 잇창명은 여자친구의 신곡을 그 누구보다 빠르게 들어보기 때문에 i집의 j번 트랙은 ai,j만큼 멋지다는 것을 당연히 알고 있다.
잇창명은 박한별을 여자친구 콘서트에 초대하고 싶어 한다. 박한별은 아직 여자친구의 곡을 들어본 적이 없기 때문에 먼저 앨범을 들어보고 괜찮은지 평가해 보아야 한다. 박한별은 앨범의 수록곡을 항상 수록된 순서대로만 들으며, 이전에 들은 어떤 여자친구 곡보다도 더 멋진 곡을 들을 때마다 1의 감동을 받는다.
잇창명은 박한별과 함께 콘서트에 가기 위해 박한별의 감동 수치를 최대화하고자 한다. 박한별에게 추천할 앨범 순서를 찾는 프로그램을 작성하여라.
입력
첫째 줄에 여자친구가 발매한 앨범의 수 n이 주어진다. (1 ≤ n ≤ 200,000)
둘째 줄부터 각 앨범의 정보가 순서대로 주어진다. 각 앨범의 정보는 두 줄에 걸쳐 주어지며, 그 중 i집에 대해 첫째 줄에는 수록된 곡의 수 ki, 둘째 줄에는 수록곡의 멋짐 수치 ai,1, ai,2, ..., ai,k_i가 공백으로 구분되어 주어진다. (1 ≤ ki ≤ 200,000, 1 ≤ ai,j ≤ 200,000)
모든 앨범의 수록곡 수의 합 Σki는 200,000곡 이하이다.
출력
박한별이 받을 수 있는 최대 감동 수치를 한 줄로 출력한다.
서브태스크
노트
예제 입력 1의 경우 4집, 2집, 3집, 1집 순서대로 듣는 것이 최적이다. 이때 박한별이 듣는 곡의 멋짐 수치는 1; 7; 8, 6; 4, 9, 4, 6, 8이 되고 4만큼의 감동을 받는다.
예제 입력 2의 경우 1집과 4집을 순서대로 듣고, 그 다음 2집과 3집은 아무 순서로 들어도 된다. 이때 박한별은 1집과 4집의 모든 곡에서 감동을 받고 2집과 3집에서는 감동을 받지 않는다.