보석 구매하기
면접 대비시간 제한2초메모리 제한128 MB
n개의 행마다 연속된 구간을 하나씩 골라 값의 총합을 최대화하고, 동점이면 구매한 보석 수가 적은 쪽, 그래도 같으면 인덱스 수열이 사전순으로 가장 작은 것을 출력합니다.
문제
보석 가게에는 여러 줄에 걸쳐 보석이 진열되어 있다. 각 보석에는 정수로 나타낸 가치가 있으며, 저주받은 보석은 음수의 가치를 가질 수도 있다.
보석은 모두 n개의 줄에 놓여 있다. 각 줄마다 비어 있지 않은 연속 구간 하나를 골라 그 구간의 보석을 구매하려고 한다. 예를 들어 한 줄에서 1번과 2번 보석을 함께 살 수 있고, 2번과 3번 보석을 함께 살 수도 있지만, 1번과 3번 보석만 따로 살 수는 없다.
구매한 모든 보석의 가치 합이 최대가 되도록 각 줄에서 살 구간을 정하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 n (1 ≤ n ≤ 1,000)이 주어진다.
이후 2×n개의 줄에 각 줄의 보석 정보가 주어진다. 각 보석 줄마다 먼저 보석의 개수 L (1 ≤ L ≤ 1,000)이 한 줄에 주어지고, 다음 줄에 보석의 가치를 나타내는 L개의 정수가 주어진다. 각 보석의 가치는 절댓값이 10,000 이하인 정수이다.
출력
첫째 줄에 구매한 보석 가치 합의 최댓값을 출력한다.
다음 n개의 줄에는 각 줄에서 몇 번째 보석부터 몇 번째 보석까지 구매했는지를 출력한다.
최댓값을 만드는 방법이 여러 가지라면, 구매한 보석의 총 개수가 가장 적은 방법을 출력한다. 그런 방법도 여러 가지라면, 출력되는 n×2개의 수를 하나의 수열로 보았을 때 사전순으로 가장 앞서는 방법을 출력한다.