시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 32 | 17 | 16 | 66.667% |
여우 Ciel은 그녀의 친구, Jiro와 함께 카드게임을 하고 있다. 책상 위에는 총 n개의 카드 묶음이 있으며, 각 카드에는 양의 정수가 하나씩 쓰여 있다.
각 플레이어는 번갈아 턴을 갖게 된다. Ciel의 턴에는 Ciel이 하나의 카드 묶음을 골라 가장 위에 있는 카드를 한 장 가진다. 반대로, Jiro의 턴에는 Jiro가 하나의 카드 묶음을 골라 가장 밑에 있는 카드를 한 장 가진다. 이렇게 번갈아 카드를 한 장씩 가져가다가, 책상 위에 더 이상 카드가 남지 않으면 게임은 종료된다.
게임이 종료되었을 때, 각 플레이어의 점수는 그 플레이어가 가져간 카드에 적힌 자연수들의 합이 된다. (만약 한 장의 카드도 가져가지 못한 플레이어가 있다면, 그 플레이어의 점수는 0이다.)두 플레이어는 모두 점수를 최대한 많이 얻고 싶어한다. 두 플레이어 모두 최적의 전략으로 카드를 가져올 때, Ciel과 Jiro가 받게 되는 점수는 각각 얼마일까?
첫 번째 줄에는 카드 묶음의 개수 n (1 ≤ n ≤ 100)이 입력으로 주어진다.
다음 n개의 줄에는 각각 자연수 si와, si개의 자연수 cij가 주어진다. (1 ≤ si ≤ 100; 1 ≤ cij ≤ 1000) 이는 i번째 카드 묶음에 카드가 총 si장 있으며, 그 순서가 입력으로 주어진 순서와 같다는 것이다. 처음 주어진 자연수가 카드 묶음의 맨 위에, 마지막에 주어진 자연수가 맨 아래 있는 카드이다.
두 플레이어가 최적의 플레이를 했을 때, 게임이 끝난 후 Ciel과 Jiro의 점수를 출력한다.
2 1 100 2 1 10
101 10
1 9 2 8 6 5 9 4 7 1 3
30 15
3 3 1 3 2 3 5 4 6 2 8 7
18 18