시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB1851028954.268%

문제

평면에 N(1 ≤ N ≤ 1,000)개의 점들이 있다. 각각의 점들은 정수 값으로 어떤 가중치 S(1 ≤ S ≤ 2,000,000)를 가지고 있다. 또 각각의 점들은 (r, c)의 좌표를 갖는데 이는 (행, 열) 순이다. 또한 1 ≤ r ≤ 2,000,000과 1 ≤ c ≤ 2,000,000가 성립한다.

이제 우리는 세로로 A(1 ≤ A ≤ 2,000,000), 가로로 B(1 ≤ B ≤ 2,000,000)만큼의 직사각형을 쳐서 이 중 몇 개의 점들을 이 사각형 안에 포함시키려고 한다. 이때, 사각형 안에 포함된 점들 중, “S의 최대-S의 최소”가 최대가 되도록 하려 한다.

예를 들어 다음과 같은 경우를 보자.

이는 예제 데이터와 같은 경우고, 회색 부분처럼 선택했을 때, 가중치 최대-가중치 최소가 7이 되고 이 경우가 이 값이 최대가 되는 경우이다.

입력

첫째 줄에 세 정수 N, A, B가 주어진다. 다음 N개의 줄에는 각 점의 r(세로좌표), c(가로좌표), S(가중치)를 나타내는 세 정수가 주어진다. 두 점이 같은 위치를 공유하는 경우는 없다.

출력

첫째 줄에 가중치 최대 - 가중치 최소가 최대가 될 경우의 이 값을 출력한다.

예제 입력 1

8 4 2
1 4 9
1 5 8
2 10 2
3 2 6
4 6 1
5 15 3
6 4 5
7 9 4

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjIxODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTAgXHVhY2UwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzYzlcdWJhNzRcdWM1ZDAgTigxICZsZTsgTiAmbGU7IDEsMDAwKVx1YWMxY1x1Yzc1OCBcdWM4MTBcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjODEwXHViNGU0XHVjNzQwIFx1YzgxNVx1YzIxOCBcdWFjMTJcdWM3M2NcdWI4NWMgXHVjNWI0XHViNWE0IFx1YWMwMFx1YzkxMVx1Y2U1OCBTKDEgJmxlOyBTICZsZTsgMiwwMDAsMDAwKVx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI2MTAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzgxMFx1YjRlNFx1Yzc0MCAociwgYylcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjIFx1YWMxNlx1YjI5NFx1YjM3MCBcdWM3NzRcdWIyOTQgKFx1ZDU4OSwgXHVjNWY0KSBcdWMyMWNcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YyAxICZsZTsgciAmbGU7IDIsMDAwLDAwMFx1YWNmYyAxICZsZTsgYyAmbGU7IDIsMDAwLDAwMFx1YWMwMCBcdWMxMzFcdWI5YmRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjMTM4XHViODVjXHViODVjIEEoMSAmbGU7IEEgJmxlOyAyLDAwMCwwMDApLCBcdWFjMDBcdWI4NWNcdWI4NWMgQigxICZsZTsgQiAmbGU7IDIsMDAwLDAwMClcdWI5Y2NcdWQwN2NcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Y2NkMFx1YzExYyBcdWM3NzQgXHVjOTExIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjODEwXHViNGU0XHVjNzQ0IFx1Yzc3NCBcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNTQ4XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YzJkY1x1ZDBhNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjMGFjXHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVjODEwXHViNGU0IFx1YzkxMSwgJmxkcXVvO1NcdWM3NTggXHVjZDVjXHViMzAwLVNcdWM3NTggXHVjZDVjXHVjMThjJnJkcXVvO1x1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWI5N2MgXHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2QwODc4NGE0LTNhZDktNDM3Ni05NjU5LTE0YmJlMzk5ZTdkZlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNDM2cHg7IGhlaWdodDogMTcycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjI5NCBcdWM2MDhcdWM4MWMgXHViMzcwXHVjNzc0XHVkMTMwXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWFjZTAsIFx1ZDY4Y1x1YzBjOSBcdWJkODBcdWJkODRcdWNjOThcdWI3ZmMgXHVjMTIwXHVkMGRkXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjOTExXHVjZTU4IFx1Y2Q1Y1x1YjMwMC1cdWFjMDBcdWM5MTFcdWNlNTggXHVjZDVjXHVjMThjXHVhYzAwIDdcdWM3NzQgXHViNDE4XHVhY2UwIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzc0IFx1YWMxMlx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTM4IFx1YzgxNVx1YzIxOCBOLCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM4MTBcdWM3NTggcihcdWMxMzhcdWI4NWNcdWM4OGNcdWQ0NWMpLCBjKFx1YWMwMFx1Yjg1Y1x1Yzg4Y1x1ZDQ1YyksIFMoXHVhYzAwXHVjOTExXHVjZTU4KVx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHViNDUwIFx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1YWNmNVx1YzcyMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjOTExXHVjZTU4IFx1Y2Q1Y1x1YjMwMCAtIFx1YWMwMFx1YzkxMVx1Y2U1OCBcdWNkNWNcdWMxOGNcdWFjMDAgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQyMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjNzc0IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjE4NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhdHRsZSBTcG90dGluZyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaXMgcGxhbm5pbmcgdG8gYnJpbmcgc29tZSBvZiBoaXMgTiAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwKSBjb3dzIHRvIHNob3cgb2ZmIGF0IHRoZSBjb3VudHkgZmFpci4gSGUgd2FudHMgdG8gYnJpbmcgdGhlIG1vc3QgZGl2ZXJzZSBjb2xsZWN0aW9uIG9mIGNvd3MgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkVhY2ggY293IGlzIGxvY2F0ZWQgb24gYSBkaXN0aW5jdCAxIHggMSBzcXVhcmUgb24gaGlzIHBsYW5hciBmaWVsZCBuYW1lZCBieSBhIHJvdyBhbmQgY29sdW1uICgxICZsdDs9IHIsYyAmbHQ7PSAyLDAwMCwwMDApLiBFYWNoIGNvdyBoYXMgUyBzcG90cyAoMSAmbHQ7PSBTICZsdDs9IDIsMDAwLDAwMCkuPFwvcD5cclxuXHJcbjxwPkZKIGlzIGdpdmVuIHR3byBpbnRlZ2VycywgQSBhbmQgQiwgYm90aCBpbiB0aGUgcmFuZ2UgMS4uMiwwMDAsMDAwLiBIZSBtYXkgY2hvb3NlIGFueSBBIHJvdyB4IEIgY29sdW1uIHJlY3Rhbmd1bGFyIGFyZWEgb2YgaGlzIGZpZWxkIGFuZCBicmluZyBhbGwgdGhlIGNvd3Mgd2l0aGluIGl0IHRvIHRoZSBmYWlyLiBUaGUgcmVjdGFuZ2xlIG11c3QgaGF2ZSBpdHMgc2lkZXMgcGFyYWxsZWwgdG8gdGhlIHggYW5kIHkgYXhlcy4gRm9yIGFueSBnaXZlbiByZWN0YW5nbGUsIHRoZSAmcXVvdDtkaXZlcnNpdHkmcXVvdDsgb2YgdGhhdCByZWN0YW5nbGUgaXMgdGhlIGFic29sdXRlIHZhbHVlIG9mIHRoZSBkaWZmZXJlbmNlIGluIHRoZSBudW1iZXIgb2Ygc3BvdHMgYmV0d2VlbiB0aGUgY293IHdpdGggdGhlIG1vc3Qgc3BvdHMgYW5kIHRoZSBjb3cgd2l0aCB0aGUgbGVhc3Qgc3BvdHMgd2l0aGluIHRoYXQgcmVjdGFuZ2xlLiBDb21wdXRlIHRoZSBtYXhpbXVtIHBvc3NpYmxlIGRpdmVyc2l0eSBhY2hpZXZlZCBvdmVyIGFsbCBwb3NzaWJsZSByZWN0YW5ndWxhciBhcmVhcy48XC9wPlxyXG5cclxuPHA+Q29uc2lkZXIgdGhpcyBmaWVsZCB3aXRoIGVpZ2h0IGNvd3Mgd2l0aCB0aGUgb2J2aW91cyBudW1iZXIgb2Ygc3BvdHMuIE4gaXMgODsgQSBpcyA0LCBCIGlzIDIuIFRoZSBiZXN0IHJlY3RhbmdsZSBpcyBtYXJrZWQ7IHRoZSBhbnN3ZXIgaXMgOC0xID0gNy48XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgIDExMTExMVxyXG4gMTIzNDU2Nzg5MDEyMzQ1XHJcbjEuLi45OHwuLi4uLi4uLi5cclxuMi4uLi58fC4uLjIuLi4uLlxyXG4zLjYuLnx8Li4uLi4uLi4uXHJcbjQuLi4ufDEuLi4uLi4uLi5cclxuNS4uLi4uLi4uLi4uLi4uM1xyXG42Li4uNS4uLi4uLi4uLi4uXHJcbjcuLi4uLi4uLjQuLi4uLi48XC9wcmU+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRocmVlIGludGVnZXJzOiBOLCBBLCBhbmQgQjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IFRocmVlIGludGVnZXJzOiByIFt0aGUgY293JiMzOTtzIHJvd10sIGMgW3RoZSBjb3cmIzM5O3MgY29sdW1uXSwgYW5kIFMgW3RoZSBudW1iZXIgb2YgdGhlIGNvdyYjMzk7cyBzcG90c108XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBtYXhpbXVtIGRpdmVyc2l0eSBhY2hpZXZlZCBvdmVyIGFsbCBwb3NzaWJsZSBBIHggQiByZWN0YW5ndWxhciBhcmVhcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2000-2001 Season > USACO Spring 2001 Contest > Green 2번

  • 문제의 오타를 찾은 사람: lyzqm