시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 65 21 21 40.385%

문제

나는 티비가 하나밖에 없는 집에 가족과 함께 살고 있다. 그래서 어떤 tv프로그램을 볼 지 늘 가족과 다투는 경우가 많다. 따라서 이를 자동으로 해결해 줄 기계을 만들고자 한다.

한 해동안 내 가족들이 보고자 하는 tv프로그램은 정해져있다. 그것들은 매주 늘 같은 시각에 시작해서 정확히 같은 시각에 끝난다. 따라서 한 주에 대해서 어떤 프로그램을 볼 지 정해놓고 그 방식대로 1년간 진행하면 되는 것이다. 각 프로그램들은 가족들로부터 일정한 점수를 받는데 이 점수가 높을 수록 가족이 선호하는 프로그램이라는 뜻이된다. 이러한 프로그램들을 볼때 점수의 총합이 가장 큰 방향으로 tv스케줄을 정하기로 가족이 합의했다. 하지만 나는 능력이 부족하여 가상의 여자친구에게 이 스케줄을 자동으로 만들어주는 기계를 만들어달라고 부탁했다. 하지만 가상의 여자친구도 이것이 귀찮아 여러분들에게 부탁을 하고자 한다.

입력

첫 번째 줄에 주어지는 t는 테스트 케이스의 개수이다. 각 테스트 케이스의 첫 줄은 tv프로그램의 개수 n(1 ≤ n ≤ 100000)이 주어진다. 그리고 n줄에 걸쳐서 공백으로 구분된 3개의 정수 s, d, p가 주어진다. s는 프로그램의 시작시간, d는 프로그램의 지속시간을 나타내고 p는 그 프로그램에 대한 가족들의 선호도이다. (0 ≤ s < s+d ≤ 10080, 1 ≤ p ≤ 2000) 만약 s+d=k라고 할때 이 프로그램은 정확히 k시각에 끝나는 것이고 새 프로그램을 정확히 k시각부터 볼 수 있다.

출력

각 테스트 케이스 별로 한줄에 선호도의 총합의 최댓값을 출력한다.

예제 입력 1

1
3
3 8 10
1 4 6
6 4 5

예제 출력 1

11

힌트

1부터 4동안 지속되는 프로그램과 6부터 4동안 진행되는 프로그램을 보면 선호도의 총합은 6+5=11이 되고 이것이 가족이 얻을 수 있는 선호도의 합의 최대가 된다.

W3sicHJvYmxlbV9pZCI6IjExMTA4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVFYgXHVjODA0XHVjN2MxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIwOThcdWIyOTQgXHVkMmYwXHViZTQ0XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YmMxNlx1YzVkMCBcdWM1YzZcdWIyOTQgXHVjOWQxXHVjNWQwIFx1YWMwMFx1Yzg3MVx1YWNmYyBcdWQ1NjhcdWFlZDggXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzViNFx1YjVhNCB0dlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWJjZmMgXHVjOWMwIFx1YjI5OCBcdWFjMDBcdWM4NzFcdWFjZmMgXHViMmU0XHVkMjJjXHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWI5Y2VcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3NzRcdWI5N2MgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1ZDU3NFx1YWNiMFx1ZDU3NCBcdWM5MDQgXHVhZTMwXHVhY2M0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWQ1NzRcdWIzZDlcdWM1NDggXHViMGI0IFx1YWMwMFx1Yzg3MVx1YjRlNFx1Yzc3NCBcdWJjZjRcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IHR2XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzgxNVx1ZDU3NFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHVhYzgzXHViNGU0XHVjNzQwIFx1YjllNFx1YzhmYyBcdWIyOTggXHVhYzE5XHVjNzQwIFx1YzJkY1x1YWMwMVx1YzVkMCBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgXHVjODE1XHVkNjU1XHVkNzg4IFx1YWMxOVx1Yzc0MCBcdWMyZGNcdWFjMDFcdWM1ZDAgXHViMDVkXHViMDljXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVkNTVjIFx1YzhmY1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNWI0XHViNWE0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWJjZmMgXHVjOWMwIFx1YzgxNVx1ZDU3NFx1YjE5M1x1YWNlMCBcdWFkZjggXHViYzI5XHVjMmRkXHViMzAwXHViODVjIDFcdWIxNDRcdWFjMDQgXHVjOWM0XHVkNTg5XHVkNTU4XHViYTc0IFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWI0ZTRcdWM3NDAgXHVhYzAwXHVjODcxXHViNGU0XHViODVjXHViZDgwXHVkMTMwIFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWM4MTBcdWMyMThcdWI5N2MgXHViYzFiXHViMjk0XHViMzcwIFx1Yzc3NCBcdWM4MTBcdWMyMThcdWFjMDAgXHViMTkyXHVjNzQ0IFx1YzIxOFx1Yjg1ZCBcdWFjMDBcdWM4NzFcdWM3NzQgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWI0ZTRcdWM3NDQgXHViY2ZjXHViNTRjIFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NzQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgdHZcdWMyYTRcdWNmMDBcdWM5MDRcdWM3NDQgXHVjODE1XHVkNTU4XHVhZTMwXHViODVjIFx1YWMwMFx1Yzg3MVx1Yzc3NCBcdWQ1NjlcdWM3NThcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWIwOThcdWIyOTQgXHViMmE1XHViODI1XHVjNzc0IFx1YmQ4MFx1Yzg3MVx1ZDU1OFx1YzVlYyBcdWFjMDBcdWMwYzFcdWM3NTggXHVjNWVjXHVjNzkwXHVjZTVjXHVhZDZjXHVjNWQwXHVhYzhjIFx1Yzc3NCBcdWMyYTRcdWNmMDBcdWM5MDRcdWM3NDQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzhmY1x1YjI5NCBcdWFlMzBcdWFjYzRcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHViMmVjXHViNzdjXHVhY2UwIFx1YmQ4MFx1ZDBjMVx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YWMwMFx1YzBjMVx1Yzc1OCBcdWM1ZWNcdWM3OTBcdWNlNWNcdWFkNmNcdWIzYzQgXHVjNzc0XHVhYzgzXHVjNzc0IFx1YWRjMFx1Y2MyZVx1YzU0NCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViZDgwXHVkMGMxXHVjNzQ0IFx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgdFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1Yzc0MCB0dlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWFjMWNcdWMyMTggbigxICZsZTsgbiAmbGU7IDEwMDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgblx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyAzXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBzLCBkLCBwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gc1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjMmRjXHVjNzkxXHVjMmRjXHVhYzA0LCBkXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWM5YzBcdWMxOGRcdWMyZGNcdWFjMDRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwIHBcdWIyOTQgXHVhZGY4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVhYzAwXHVjODcxXHViNGU0XHVjNzU4IFx1YzEyMFx1ZDYzOFx1YjNjNFx1Yzc3NFx1YjJlNC4gKDAgJmxlOyBzICZsdDsgcytkICZsZTsgMTAwODAsIDEgJmxlOyBwICZsZTsgMjAwMCkgXHViOWNjXHVjNTdkIHMrZD1rXHViNzdjXHVhY2UwIFx1ZDU2MFx1YjU0YyBcdWM3NzQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBrXHVjMmRjXHVhYzAxXHVjNWQwIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWFjODNcdWM3NzRcdWFjZTAgXHVjMGM4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM4MTVcdWQ2NTVcdWQ3ODgga1x1YzJkY1x1YWMwMVx1YmQ4MFx1ZDEzMCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjYzRcdWI4NWMgXHVkNTVjXHVjOTA0XHVjNWQwIFx1YzEyMFx1ZDYzOFx1YjNjNFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+MVx1YmQ4MFx1ZDEzMCA0XHViM2Q5XHVjNTQ4IFx1YzljMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWFjZmMgNlx1YmQ4MFx1ZDEzMCA0XHViM2Q5XHVjNTQ4IFx1YzljNFx1ZDU4OVx1YjQxOFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViY2Y0XHViYTc0IFx1YzEyMFx1ZDYzOFx1YjNjNFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDAgNis1PTExXHVjNzc0IFx1YjQxOFx1YWNlMCBcdWM3NzRcdWFjODNcdWM3NzQgXHVhYzAwXHVjODcxXHVjNzc0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzEyMFx1ZDYzOFx1YjNjNFx1Yzc1OCBcdWQ1NjlcdWM3NTggXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMTA4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVFYgQmF0dGxlIiwiZGVzY3JpcHRpb24iOiI8cD5UbyB5b3VyIGltbWVuc2UgZnJ1c3RyYXRpb24sIHlvdSBvbmx5IGhhdmUgb25lIHRlbGV2aXNpb24gc2V0IGluIHlvdXIgZmFtaWx5LiBEZWNpZGluZyB3aGF0IFRWIHNob3cgdG8gd2F0Y2ggYXQgYW55IGdpdmVuIHRpbWUgaXMgdGhlIHNvdXJjZSBvZiBhIGxvdCBvZiBhcmd1bWVudC4gQXMgYW4gZXhhbXBsZSwgeW91ciBsaXR0bGUgc2lzdGVyIEFubmUgYWx3YXlzIHdhbnRzIHRvIHdhdGNoICZyZHF1bztEZXNwZXJhdGUgSG91c2V3aXZlcyZyZHF1bzsgd2hpbGUgeW91IHdhbnQgdG8gd2F0Y2ggJnJkcXVvO0MuUy5JLiZyZHF1bzsuIFlvdSBiZWxpZXZlIGl0IHdvdWxkIGJlIGJlbmVmaWNpYWwgdG8gdXNlIGF1dG9tYXRlZCB0b29scyB0byBzZXR0bGUgdGhlc2UgYXJndW1lbnRzLjxcL3A+XHJcblxyXG48cD5Zb3UgdGhlcmVmb3JlIGRlY2lkZSB0byBjb25zdHJ1Y3QgYSBzeXN0ZW0gdGhhdCB3aWxsIGRlY2lkZSB3aGljaCBzaG93IHRoYXQgc2hvdWxkIGJlIG9uIGF0IGFueSBnaXZlbiBwb2ludCBpbiB0aW1lLiBEdXJpbmcgYSBzZWFzb24gZWFjaCBzaG93IGlzIHR5cGljYWxseSBzZW50IG9uIHRoZSBleGFjdCBzYW1lIHRpbWUgZWFjaCB3ZWVrLiBZb3UgdGhlcmVmb3JlIGRlY2lkZSB0byBzb2x2ZSB0aGlzIHByb2JsZW0gZm9yIG9uZSB3ZWVrLCBhbmQgbGV0IHRoaXMgc29sdXRpb24gZGVjaWRlIGZvciBhIHdob2xlIHNlYXNvbi4gRWFjaCBtZW1iZXIgb2YgdGhlIGZhbWlseSBpcyBnaXZlbiB5IHBvaW50cyB3aGljaCBoZVwvc2hlIGNhbiBkaXN0cmlidXRlIGFtb25nIGhpc1wvaGVyIGZhdm9yaXRlIHNob3dzLiBXZSBhc3N1bWUgdGhhdCBlYWNoIHNob3cgc3RhcnRzIGF0IHRoZSBzYW1lIHRpbWUgYW5kIGxhc3RzIGZvciBkIGNvbnNlY3V0aXZlIG1pbnV0ZXMgZWFjaCB3ZWVrLiBFYWNoIFRWIHNob3cgaXMgdGhlbiBhc3NpZ25lZCB0aGUgdG90YWwgbnVtYmVyIG9mIHBvaW50cyBnaXZlbiB0byBpdCBieSBhbGwgZmFtaWx5IG1lbWJlcnMgaW4gdG90YWwuIFlvdSBzaG91bGQgd3JpdGUgYSBwcm9ncmFtIHRoYXQgbWF4aW1pemVzIHRoZSB0b3RhbCBudW1iZXIgb2YgcG9pbnRzIG9mIHRoZSBUViBzaG93cyBzaG93biBvbiB5b3VyIHRlbGV2aXNpb24gc2V0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZ2l2ZXMgMSAmbGU7IHQgJmxlOyAzMCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UgZ2l2ZXMgMSAmbGU7IG4gJmxlOyAxMDAwMDAsIHRoZSBudW1iZXIgb2YgVFYgc2hvd3MgdGhhdCBoYXZlIGdvdHRlbiBhbnkgcG9pbnRzIGZyb20geW91ciBmYW1pbHkuIFRoZW4gZm9sbG93IG4gbGluZXMgd2l0aCAzIHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2VycyBzPHN1Yj5pPFwvc3ViPiwgZDxzdWI+aTxcL3N1Yj4gYW5kIHA8c3ViPmk8XC9zdWI+LCB3aGVyZSBlYWNoIGxpbmUgZGVzY3JpYmVzIG9uZSBUViBzaG93LiBzPHN1Yj5pPFwvc3ViPiBkZXNjcmliZXMgdGhlIG1pbnV0ZSBhdCB3aGljaCBzaG93IGkgc3RhcnRzLCBhbmQgZDxzdWI+aTxcL3N1Yj4gZGVzY3JpYmVzIHRoZSBudW1iZXIgb2YgbWludXRlcyBzaG93IGkgbGFzdHMgKDAgJmxlOyBzPHN1Yj5pPFwvc3ViPiAmbHQ7IHM8c3ViPmk8XC9zdWI+ICsgZDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDA4MCkuIElmIHM8c3ViPmk8XC9zdWI+ICsgZDxzdWI+aTxcL3N1Yj4gPSBrLCBpdCBtZWFucyB0aGF0IHlvdSBjYW4gc3RhcnQgd2F0Y2hpbmcgYSBuZXcgc2hvdyBhdCB0aW1lIGsuIHA8c3ViPmk8XC9zdWI+IGRlc2NyaWJlcyB0aGUgdG90YWwgbnVtYmVyIG9mIHBvaW50cyBzaG93IGkgaGFzIGdvdHRlbiBpbiB5b3VyIGZhbWlseSAoMSAmbGU7IHA8c3ViPmk8XC9zdWI+ICZsZTsgMjAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlcmUgc2hvdWxkIGJlIG9uZSBsaW5lIG9mIG91dHB1dCBmb3IgZWFjaCB0ZXN0IGNhc2UgY29udGFpbmluZyB0aGUgbWF4aW11bSBzdW0gb2YgcG9pbnRzIGZvciB0aGUgVFYgc2hvd3Mgc2hvd24gb24gdGhlIHRlbGV2aXNpb24gc2V0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > IDI Open Contest > IDI Open 2008 B번

  • 문제의 오타를 찾은 사람: Green55
  • 문제를 번역한 사람: petil777