시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 316 | 58 | 45 | 21.951% |
상근이는 자신의 이름을 딴 방송국 GSK를 만들었다. GSK는 스포츠 전문 방송국으로 곧 열리는 경기 N개를 모두 취재하려고 한다.
각각의 스포츠 경기 Ei(1 ≤ i ≤ n)의 시작 시간은 si, 경기 시간은 di, 경기장은 gi이다. gi에서 gj로 가는 이동 시간은 ti,j(1 ≤ i,j ≤ n)이며, ti,j = tj,i와 ti,j ≤ ti,k + tk,j (1 ≤ i,j,k ≤ n)을 만족한다.
리포터는 경기가 열리는 동안 그 경기장에서 계속 취재를 해야 한다. 즉, 한 리포터가 두 경기 Ei와 Ej를 취재하려면, si + di + ti,j ≤ sj 나 sj + dj + tj,i ≤ si를 만족해야 한다.
경기 정보가 모두 주어졌을 때, 한 리포터가 동시에 취재할 수 없는 가장 큰 경기의 부분집합을 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 경기의 수 n (1 ≤ n ≤ 1,000)이 주어진다. 둘째 줄에는 각 경기의 시작 시간 si, 셋째 줄에는 경기 시간 di가 주어진다. (1 ≤ si, di ≤ 1,000,000) 넷째 줄부터 총 n개 줄 중 i번째 줄에는 n-i+1개의 정수가 주어지며, ti,i, ti,i+1, ..., ti,n을 나타낸다. (0 ≤ ti,j ≤ 1,000,000) ti,i는 항상 0이다.
각 테스트 케이스마다 두 줄을 출력한다. 첫째 줄은 한 리포터가 동시에 취재할 수 없는 가장 큰 경기의 부분집합의 크기 k이고, 둘째 줄에는 집합에 포함된 경기의 번호를 출력한다. (Ei에서 i) 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
2 3 7 8 9 1 1 1 0 2 2 0 1 0 2 7 12 3 2 0 2 0
3 2 3 1 1 2
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2012 K번