시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 220 33 27 18.243%

문제

상근이는 자신의 이름을 딴 방송국 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+XHVjNWQwXHVjMTFjIGkpIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg4OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTcG9ydHMgUmVwb3J0ZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5BIG5ld3MgYWdlbmN5IHdpc2hlcyB0byBjb3ZlciBzcG9ydGluZyBldmVudHMgdGhhdCB3aWxsIHRha2UgcGxhY2Ugc29vbi4gRm9yIGVhY2ggZXZlbnQgRTxzdWI+aTxcL3N1Yj4sIDEgJmxlOyBpICZsZTsgbiwgaXRzIHN0YXJ0aW5nIHRpbWUgczxzdWI+aTxcL3N1Yj4sIGR1cmF0aW9uIHRpbWUgZDxzdWI+aTxcL3N1Yj4sIGFuZCBnZW9ncmFwaGljYWwgc2l0ZSBnPHN1Yj5pPFwvc3ViPiBhcmUga25vd24gaW4gYWR2YW5jZS4gSW4gYWRkaXRpb24sIHRoZSB0cmF2ZWwgdGltZSB0PHN1Yj5pLGo8XC9zdWI+IGZyb20gZzxzdWI+aTxcL3N1Yj4gdG8gZzxzdWI+ajxcL3N1Yj4gaXMgYWxzbyBrbm93biBmb3IgYWxsIDEgJmxlOyBpLGogJmxlOyBuLCB3aGVyZSB0PHN1Yj5pLGo8XC9zdWI+ID0gdDxzdWI+aixpPFwvc3ViPiBhbmQgdDxzdWI+aSxqPFwvc3ViPiAmbGU7IHQ8c3ViPmksazxcL3N1Yj4gKyB0PHN1Yj5rLGo8XC9zdWI+IGZvciBldmVyeSAxICZsZTsgaSxqLGsgJmxlOyBuLiBJbiBnYXRoZXJpbmcgbmV3cyBmcm9tIGFuIGV2ZW50LCB0aGUgbmV3cyBhZ2VuY3kgd2FudHMgb25lIHJlcG9ydGVyIHRvIGZ1bGx5IHRha2UgcmVzcG9uc2liaWxpdHkgZm9yIHRoZSBlbnRpcmUgcGVyaW9kIG9mIHRoZSBldmVudC4gVGhpcyBtZWFucyB0aGF0IHR3byBldmVudHMgRTxzdWI+aTxcL3N1Yj4gYW5kIEU8c3ViPmo8XC9zdWI+IG1heSBiZSBhc3NpZ25lZCB0byB0aGUgc2FtZSByZXBvcnRlciBpZiBzPHN1Yj5pPFwvc3ViPiZuYnNwOysgZDxzdWI+aTxcL3N1Yj4mbmJzcDsrIHQ8c3ViPmksajxcL3N1Yj4mbmJzcDsmbGU7IHM8c3ViPmo8XC9zdWI+IG9yIHM8c3ViPmo8XC9zdWI+Jm5ic3A7KyBkPHN1Yj5qPFwvc3ViPiZuYnNwOysgdDxzdWI+aixpPFwvc3ViPiZuYnNwOyZsZTsgczxzdWI+aTxcL3N1Yj4uJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcblVuZGVyIHRoZXNlIGNvbnN0cmFpbnRzLCBhIG1hbmFnZXIgb2YgdGhlIGFnZW5jeSB0cmllcyB0byBpZGVudGlmeSBhIG1heGltdW0gc3Vic2V0IG9mIGV2ZW50cyBzdWNoIHRoYXQgbm8gcGFpciBvZiBldmVudHMgaW4gdGhlIHN1YnNldCBjYW4gYmUgYXNzaWduZWQgdG8gdGhlIHNhbWUgcmVwb3J0ZXIuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IHNvbHZlcyB0aGUgbWFuYWdlciZyc3F1bztzIHByb2JsZW0uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGlzIGRlc2NyaWJlZCBieSBhIG51bWJlciBvZiBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgYW4gaW50ZWdlciBuLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2Ygc3BvcnRpbmcgZXZlbnRzICgxICZsZTsgbiAmbGU7IDEsMDAwKS4gVGhlbiwgdGhlIHNlY29uZCBsaW5lIG4gY29udGFpbnMgaW50ZWdlcnMgczxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCAuLi4sIHM8c3ViPm48XC9zdWI+IHNlcGFyYXRlZCBieSBzcGFjZXMsIHdoZXJlIHM8c3ViPmk8XC9zdWI+IGlzIHRoZSBzdGFydGluZyB0aW1lIG9mIGV2ZW50IEU8c3ViPmk8XC9zdWI+ICgxICZsZTsgczxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDApLiBTaW1pbGFyeSwgdGhlIHRoaXJkIGxpbmUgY29udGFpbnMgbiBpbnRlZ2VycyBkPHN1Yj4xPFwvc3ViPiwgZDxzdWI+MjxcL3N1Yj4sIC4uLiwgZDxzdWI+bjxcL3N1Yj4sIHdoZXJlIGQ8c3ViPmk8XC9zdWI+IGlzIHRoZSBkdXJhdGlvbiB0aW1lIG9mIEU8c3ViPmk8XC9zdWI+ICgxICZsZTsgZDxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDApLiBJbiB0aGUgZm9sbG93aW5nIG4gbGluZXMsIHRoZSBpLXRoIGxpbmUgY29udGFpbnMgbi1pKzEgaW50ZWdlcnMgdDxzdWI+aSxpPFwvc3ViPiwgdDxzdWI+aSxpKzE8XC9zdWI+LCAuLi4sIHQ8c3ViPmksbjxcL3N1Yj4sIHdoZXJlIHQ8c3ViPmksajxcL3N1Yj4gaXMgdGhlIHRyYXZlbCB0aW1lIGZyb20gZzxzdWI+aTxcL3N1Yj4gdG8gZzxzdWI+ajxcL3N1Yj4gKDAgJmxlOyB0PHN1Yj5pLGo8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKS4gWW91IG1heSBhc3N1bWUgdDxzdWI+aSxpPFwvc3ViPiA9IDAgZm9yIGV2ZXJ5IGkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSB0d28gbGluZXMgcGVyIGVhY2ggdGVzdCBjYXNlLiBUaGUgZmlyc3QgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbWF4aW11bSBudW1iZXIgayBvZiBldmVudHMgaW4gd2hpY2ggbm8gdHdvIGNhbiBiZSBhc3NpZ25lZCB0byB0aGUgc2FtZSByZXBvcnRlci4gVGhlbiwgdGhlIHNlY29uZCBsaW5lIHNob3VsZCBjb250YWluIHRoZSBpbmRpY2VzIG9mIHN1Y2ggayBldmVudHMgKGkuZS4sIGkgZm9yIEU8c3ViPmk8XC9zdWI+KSwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIElmIHRoZXJlIGFyZSBtdWx0aXBsZSBzb2x1dGlvbnMsIGp1c3Qgb3V0cHV0IGFueSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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