시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB316584521.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) 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

2
3
7 8 9
1 1 1
0 2 2
0 1
0
2
7 12
3 2
0 2
0

예제 출력 1

3
2 3 1
1
2
W3sicHJvYmxlbV9pZCI6Ijg4OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWQzZWNcdWNlMjAgXHVjODA0XHViYjM4IFx1Y2M0NFx1YjExMCBHU0siLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQ0IFx1YjUzNCBcdWJjMjlcdWMxYTFcdWFkNmQgR1NLXHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gR1NLXHViMjk0IFx1YzJhNFx1ZDNlY1x1Y2UyMCBcdWM4MDRcdWJiMzggXHViYzI5XHVjMWExXHVhZDZkXHVjNzNjXHViODVjIFx1YWNlNyBcdWM1ZjRcdWI5YWNcdWIyOTQgXHVhY2JkXHVhZTMwIE5cdWFjMWNcdWI5N2MgXHViYWE4XHViNDUwIFx1Y2RlOFx1YzdhY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyYTRcdWQzZWNcdWNlMjAgXHVhY2JkXHVhZTMwIEU8c3ViPmk8XC9zdWI+KDEgJmxlOyBpICZsZTsgbilcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzJkY1x1YWMwNFx1Yzc0MCBzPHN1Yj5pPFwvc3ViPiwgXHVhY2JkXHVhZTMwIFx1YzJkY1x1YWMwNFx1Yzc0MCBkPHN1Yj5pPFwvc3ViPiwgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQwIGc8c3ViPmk8XC9zdWI+XHVjNzc0XHViMmU0LiBnPHN1Yj5pPFwvc3ViPlx1YzVkMFx1YzExYyBnPHN1Yj5qPFwvc3ViPlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjNzc0XHViM2Q5IFx1YzJkY1x1YWMwNFx1Yzc0MCB0PHN1Yj5pLGo8XC9zdWI+KDEgJmxlOyBpLGogJmxlOyBuKVx1Yzc3NFx1YmE3MCwgdDxzdWI+aSxqPFwvc3ViPiA9IHQ8c3ViPmosaTxcL3N1Yj5cdWM2NDAgdDxzdWI+aSxqPFwvc3ViPiAmbGU7IHQ8c3ViPmksazxcL3N1Yj4gKyB0PHN1Yj5rLGo8XC9zdWI+ICgxICZsZTsgaSxqLGsgJmxlOyBuKVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjlhY1x1ZDNlY1x1ZDEzMFx1YjI5NCBcdWFjYmRcdWFlMzBcdWFjMDAgXHVjNWY0XHViOWFjXHViMjk0IFx1YjNkOVx1YzU0OCBcdWFkZjggXHVhY2JkXHVhZTMwXHVjN2E1XHVjNWQwXHVjMTFjIFx1YWNjNFx1YzE4ZCBcdWNkZThcdWM3YWNcdWI5N2MgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWQ1NWMgXHViOWFjXHVkM2VjXHVkMTMwXHVhYzAwIFx1YjQ1MCBcdWFjYmRcdWFlMzAgRTxzdWI+aTxcL3N1Yj5cdWM2NDAgRTxzdWI+ajxcL3N1Yj5cdWI5N2MgXHVjZGU4XHVjN2FjXHVkNTU4XHViODI0XHViYTc0LCBzPHN1Yj5pPFwvc3ViPiArIGQ8c3ViPmk8XC9zdWI+ICsgdDxzdWI+aSxqPFwvc3ViPiAmbGU7IHM8c3ViPmo8XC9zdWI+IFx1YjA5OCBzPHN1Yj5qPFwvc3ViPiArIGQ8c3ViPmo8XC9zdWI+ICsgdDxzdWI+aixpPFwvc3ViPiAmbGU7IHM8c3ViPmk8XC9zdWI+XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1YWUzMCBcdWM4MTVcdWJjZjRcdWFjMDAgXHViYWE4XHViNDUwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDU1YyBcdWI5YWNcdWQzZWNcdWQxMzBcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Y2RlOFx1YzdhY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YzIxOCBuICgxICZsZTsgbiAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0IHM8c3ViPmk8XC9zdWI+LCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNiZFx1YWUzMCBcdWMyZGNcdWFjMDQgZDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IHM8c3ViPmk8XC9zdWI+LCBkPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCkgXHViMTM3XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWNkMWQgblx1YWMxYyBcdWM5MDQgXHVjOTExIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG4taSsxXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIHQ8c3ViPmksaTxcL3N1Yj4sIHQ8c3ViPmksaSsxPFwvc3ViPiwgLi4uLCB0PHN1Yj5pLG48XC9zdWI+XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gKDAgJmxlOyB0PHN1Yj5pLGo8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKSB0PHN1Yj5pLGk8XC9zdWI+XHViMjk0IFx1ZDU2ZFx1YzBjMSAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjQ1MCBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIFx1ZDU1YyBcdWI5YWNcdWQzZWNcdWQxMzBcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Y2RlOFx1YzdhY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWQwNmNcdWFlMzAmbmJzcDtrXHVjNzc0XHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzlkMVx1ZDU2OVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMmbmJzcDtcdWFjYmRcdWFlMzBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKEU8c3ViPmk8XC9zdWI+XHVjNWQwXHVjMTFjIGkpIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI4ODk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3BvcnRzIFJlcG9ydGVycyIsImRlc2NyaXB0aW9uIjoiPHA+QSBuZXdzIGFnZW5jeSB3aXNoZXMgdG8gY292ZXIgc3BvcnRpbmcgZXZlbnRzIHRoYXQgd2lsbCB0YWtlIHBsYWNlIHNvb24uIEZvciBlYWNoIGV2ZW50IEU8c3ViPmk8XC9zdWI+LCAxICZsZTsgaSAmbGU7IG4sIGl0cyBzdGFydGluZyB0aW1lIHM8c3ViPmk8XC9zdWI+LCBkdXJhdGlvbiB0aW1lIGQ8c3ViPmk8XC9zdWI+LCBhbmQgZ2VvZ3JhcGhpY2FsIHNpdGUgZzxzdWI+aTxcL3N1Yj4gYXJlIGtub3duIGluIGFkdmFuY2UuIEluIGFkZGl0aW9uLCB0aGUgdHJhdmVsIHRpbWUgdDxzdWI+aSxqPFwvc3ViPiBmcm9tIGc8c3ViPmk8XC9zdWI+IHRvIGc8c3ViPmo8XC9zdWI+IGlzIGFsc28ga25vd24gZm9yIGFsbCAxICZsZTsgaSxqICZsZTsgbiwgd2hlcmUgdDxzdWI+aSxqPFwvc3ViPiA9IHQ8c3ViPmosaTxcL3N1Yj4gYW5kIHQ8c3ViPmksajxcL3N1Yj4gJmxlOyB0PHN1Yj5pLGs8XC9zdWI+ICsgdDxzdWI+ayxqPFwvc3ViPiBmb3IgZXZlcnkgMSAmbGU7IGksaixrICZsZTsgbi4gSW4gZ2F0aGVyaW5nIG5ld3MgZnJvbSBhbiBldmVudCwgdGhlIG5ld3MgYWdlbmN5IHdhbnRzIG9uZSByZXBvcnRlciB0byBmdWxseSB0YWtlIHJlc3BvbnNpYmlsaXR5IGZvciB0aGUgZW50aXJlIHBlcmlvZCBvZiB0aGUgZXZlbnQuIFRoaXMgbWVhbnMgdGhhdCB0d28gZXZlbnRzIEU8c3ViPmk8XC9zdWI+IGFuZCBFPHN1Yj5qPFwvc3ViPiBtYXkgYmUgYXNzaWduZWQgdG8gdGhlIHNhbWUgcmVwb3J0ZXIgaWYgczxzdWI+aTxcL3N1Yj4mbmJzcDsrIGQ8c3ViPmk8XC9zdWI+Jm5ic3A7KyB0PHN1Yj5pLGo8XC9zdWI+Jm5ic3A7JmxlOyBzPHN1Yj5qPFwvc3ViPiBvciBzPHN1Yj5qPFwvc3ViPiZuYnNwOysgZDxzdWI+ajxcL3N1Yj4mbmJzcDsrIHQ8c3ViPmosaTxcL3N1Yj4mbmJzcDsmbGU7IHM8c3ViPmk8XC9zdWI+LiZuYnNwOzxiciBcLz5cclxuJm5ic3A7PGJyIFwvPlxyXG5VbmRlciB0aGVzZSBjb25zdHJhaW50cywgYSBtYW5hZ2VyIG9mIHRoZSBhZ2VuY3kgdHJpZXMgdG8gaWRlbnRpZnkgYSBtYXhpbXVtIHN1YnNldCBvZiBldmVudHMgc3VjaCB0aGF0IG5vIHBhaXIgb2YgZXZlbnRzIGluIHRoZSBzdWJzZXQgY2FuIGJlIGFzc2lnbmVkIHRvIHRoZSBzYW1lIHJlcG9ydGVyLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBzb2x2ZXMgdGhlIG1hbmFnZXImcnNxdW87cyBwcm9ibGVtLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBpcyBkZXNjcmliZWQgYnkgYSBudW1iZXIgb2YgbGluZXMuIFRoZSBmaXJzdCBsaW5lIG9mIGEgdGVzdCBjYXNlIGNvbnRhaW5zIGFuIGludGVnZXIgbiwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHNwb3J0aW5nIGV2ZW50cyAoMSAmbGU7IG4gJmxlOyAxLDAwMCkuIFRoZW4sIHRoZSBzZWNvbmQgbGluZSBuIGNvbnRhaW5zIGludGVnZXJzIHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgLi4uLCBzPHN1Yj5uPFwvc3ViPiBzZXBhcmF0ZWQgYnkgc3BhY2VzLCB3aGVyZSBzPHN1Yj5pPFwvc3ViPiBpcyB0aGUgc3RhcnRpbmcgdGltZSBvZiBldmVudCBFPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IHM8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKS4gU2ltaWxhcnksIHRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG4gaW50ZWdlcnMgZDxzdWI+MTxcL3N1Yj4sIGQ8c3ViPjI8XC9zdWI+LCAuLi4sIGQ8c3ViPm48XC9zdWI+LCB3aGVyZSBkPHN1Yj5pPFwvc3ViPiBpcyB0aGUgZHVyYXRpb24gdGltZSBvZiBFPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGQ8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKS4gSW4gdGhlIGZvbGxvd2luZyBuIGxpbmVzLCB0aGUgaS10aCBsaW5lIGNvbnRhaW5zIG4taSsxIGludGVnZXJzIHQ8c3ViPmksaTxcL3N1Yj4sIHQ8c3ViPmksaSsxPFwvc3ViPiwgLi4uLCB0PHN1Yj5pLG48XC9zdWI+LCB3aGVyZSB0PHN1Yj5pLGo8XC9zdWI+IGlzIHRoZSB0cmF2ZWwgdGltZSBmcm9tIGc8c3ViPmk8XC9zdWI+IHRvIGc8c3ViPmo8XC9zdWI+ICgwICZsZTsgdDxzdWI+aSxqPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCkuIFlvdSBtYXkgYXNzdW1lIHQ8c3ViPmksaTxcL3N1Yj4gPSAwIGZvciBldmVyeSBpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgdHdvIGxpbmVzIHBlciBlYWNoIHRlc3QgY2FzZS4gVGhlIGZpcnN0IGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG1heGltdW0gbnVtYmVyIGsgb2YgZXZlbnRzIGluIHdoaWNoIG5vIHR3byBjYW4gYmUgYXNzaWduZWQgdG8gdGhlIHNhbWUgcmVwb3J0ZXIuIFRoZW4sIHRoZSBzZWNvbmQgbGluZSBzaG91bGQgY29udGFpbiB0aGUgaW5kaWNlcyBvZiBzdWNoIGsgZXZlbnRzIChpLmUuLCBpIGZvciBFPHN1Yj5pPFwvc3ViPiksIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgc29sdXRpb25zLCBqdXN0IG91dHB1dCBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2012 K번