시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB72022419533.679%

문제

어떠한 다이아몬드의 가치는 그 다이아몬드의 중량인 캐럿과 선명도에 의해서 결정됩니다. 즉, 작지만 선명한 다이아몬드가 크고 선명하지 않은 다이아몬드보다는 가치가 높습니다. 다이아몬드의 선명도는 0.0-10.0의 스캐일로 표현할 수 있는데, 0.0의 선명도는 완벽하게 선명한 다이아몬드를 나타내고 10.0은 가장 결함이 많은 다이아몬드를 나타냅니다.

N개의 다이아몬드의 중량 wi와 선명도 ci의 정보가 주어졌을때, 이 중에서 다이아몬드의 중량이 높아지고, 선명도 값이 낮아지는 부분열 중 최장의 것의 길이를 구하세요. 예를들어 주어진 정보가 다음과 같다면

wi ci
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5

다이아몬드 중량이 높아지고, 선명도 값이 낮아지는 부분열 중 길이가 최장인 것은 다음과 같습니다.

1.5 9.0
2.5 6.0
3.0 5.0
4.0 2.0

왜냐하면 표에 나와있는 부분열을 보면, 무게는 증가하고, 선명도의 값은 감소하기 때문입니다.

입력

테스트 케이스의 개수 T가 주어지고 (1≤T≤100) 각 테스트 케이스마다 다이아몬드의 정보의 개수 N (1≤N≤200)이 주어집니다. 그리고 N개의 줄에 걸쳐서 다이아몬드의 무게와 선명도 wi, ci가 주어집니다 (0≤wi,ci≤100).

출력

각 테스트 케이스마다 다이아몬드의 가치가 높아지는 부분열중 최장의 것의 길이를 구하세요.

예제 입력 1

3
2
1.0 1.0
1.5 0.0
3
1.0 1.0
1.0 1.0
1.0 1.0
6
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5

예제 출력 1

2
1
4
W3sicHJvYmxlbV9pZCI6IjEwNTcxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZGlhbW9uZC5wbmdcIiBzdHlsZT1cImhlaWdodDo3MnB4OyB3aWR0aDoyMTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTBcdWQ1NWMgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YWMwMFx1Y2U1OFx1YjI5NCBcdWFkZjggXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YzkxMVx1YjdjOVx1Yzc3OCBcdWNlOTBcdWI3ZmZcdWFjZmMgXHVjMTIwXHViYTg1XHViM2M0XHVjNWQwIFx1Yzc1OFx1ZDU3NFx1YzExYyBcdWFjYjBcdWM4MTVcdWI0MjlcdWIyYzhcdWIyZTQuIFx1Yzk4OSwgXHVjNzkxXHVjOWMwXHViOWNjIFx1YzEyMFx1YmE4NVx1ZDU1YyBcdWIyZTRcdWM3NzRcdWM1NDRcdWJhYWNcdWI0ZGNcdWFjMDAgXHVkMDZjXHVhY2UwIFx1YzEyMFx1YmE4NVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHViY2Y0XHViMmU0XHViMjk0IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWIxOTJcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YjJlNFx1Yzc3NFx1YzU0NFx1YmFhY1x1YjRkY1x1Yzc1OCBcdWMxMjBcdWJhODVcdWIzYzRcdWIyOTQgMC4wLTEwLjBcdWM3NTggXHVjMmE0XHVjZTkwXHVjNzdjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCAwLjBcdWM3NTggXHVjMTIwXHViYTg1XHViM2M0XHViMjk0IFx1YzY0NFx1YmNiZFx1ZDU1OFx1YWM4YyBcdWMxMjBcdWJhODVcdWQ1NWMgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCAxMC4wXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWFjYjBcdWQ1NjhcdWM3NzQgXHViOWNlXHVjNzQwIFx1YjJlNFx1Yzc3NFx1YzU0NFx1YmFhY1x1YjRkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYzVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YzkxMVx1YjdjOSB3PHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWMxMjBcdWJhODVcdWIzYzQgYzxzdWI+aTxcL3N1Yj5cdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YywgXHVjNzc0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWIyZTRcdWM3NzRcdWM1NDRcdWJhYWNcdWI0ZGNcdWM3NTggXHVjOTExXHViN2M5XHVjNzc0IFx1YjE5Mlx1YzU0NFx1YzljMFx1YWNlMCwgXHVjMTIwXHViYTg1XHViM2M0IFx1YWMxMlx1Yzc3NCBcdWIwYWVcdWM1NDRcdWM5YzBcdWIyOTQgXHViZDgwXHViZDg0XHVjNWY0IFx1YzkxMSBcdWNkNWNcdWM3YTVcdWM3NTggXHVhYzgzXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWMxMzhcdWM2OTQuIFx1YzYwOFx1Yjk3Y1x1YjRlNFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODE1XHViY2Y0XHVhYzAwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTRcdWJhNzQ8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOiAzMCU7XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+dzxzdWI+aTxcL3N1Yj48XC90ZD5cclxuXHRcdFx0PHRkPmM8c3ViPmk8XC9zdWI+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEuNTxcL3RkPlxyXG5cdFx0XHQ8dGQ+OS4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjIuMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+Mi4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjIuNTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Ni4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjMuMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NS4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQuMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+Mi4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEwLjA8XC90ZD5cclxuXHRcdFx0PHRkPjUuNTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjIFx1YzkxMVx1YjdjOVx1Yzc3NCBcdWIxOTJcdWM1NDRcdWM5YzBcdWFjZTAsIFx1YzEyMFx1YmE4NVx1YjNjNCBcdWFjMTJcdWM3NzQgXHViMGFlXHVjNTQ0XHVjOWMwXHViMjk0IFx1YmQ4MFx1YmQ4NFx1YzVmNCBcdWM5MTEgXHVhZTM4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzdhNVx1Yzc3OCBcdWFjODNcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOiAzMCU7XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MS41PFwvdGQ+XHJcblx0XHRcdDx0ZD45LjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+Mi41PFwvdGQ+XHJcblx0XHRcdDx0ZD42LjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+My4wPFwvdGQ+XHJcblx0XHRcdDx0ZD41LjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NC4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4yLjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YzY1Y1x1YjBkMFx1ZDU1OFx1YmE3NCBcdWQ0NWNcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1YzVmNFx1Yzc0NCBcdWJjZjRcdWJhNzQsIFx1YmIzNFx1YWM4Y1x1YjI5NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWFjZTAsIFx1YzEyMFx1YmE4NVx1YjNjNFx1Yzc1OCBcdWFjMTJcdWM3NDAgXHVhYzEwXHVjMThjXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwICgxJmxlO1QmbGU7MTAwKSBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWIyZTRcdWM3NzRcdWM1NDRcdWJhYWNcdWI0ZGNcdWM3NTggXHVjODE1XHViY2Y0XHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxJmxlO04mbGU7MjAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YmIzNFx1YWM4Y1x1YzY0MCBcdWMxMjBcdWJhODVcdWIzYzQgdzxzdWI+aSwgPFwvc3ViPmM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNCAoMCZsZTt3PHN1Yj5pLDxcL3N1Yj5jPHN1Yj5pPFwvc3ViPiZsZTsxMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjJlNFx1Yzc3NFx1YzU0NFx1YmFhY1x1YjRkY1x1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgXHViMTkyXHVjNTQ0XHVjOWMwXHViMjk0IFx1YmQ4MFx1YmQ4NFx1YzVmNFx1YzkxMSBcdWNkNWNcdWM3YTVcdWM3NTggXHVhYzgzXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA1NzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEaWFtb25kcyIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2RpYW1vbmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzJweDsgd2lkdGg6MjEwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSBkaWFtb25kJnJzcXVvO3Mgb3ZlcmFsbCB3b3J0aCBpcyBkZXRlcm1pbmVkIGJ5IGl0cyBtYXNzIGluIGNhcmF0cyBhcyB3ZWxsIGFzIGl0cyBvdmVyYWxsIGNsYXJpdHkuIEEgbGFyZ2UgZGlhbW9uZCB3aXRoIG1hbnkgaW1wZXJmZWN0aW9ucyBpcyBub3Qgd29ydGggYXMgbXVjaCBhcyBhIHNtYWxsZXIsIGZsYXdsZXNzIGRpYW1vbmQuIFRoZSBvdmVyYWxsIGNsYXJpdHkgb2YgYSBkaWFtb25kIGNhbiBiZSBkZXNjcmliZWQgb24gYSBzY2FsZSBmcm9tIDAuMCZuZGFzaDsxMC4wIGFkb3B0ZWQgYnkgdGhlIEFtZXJpY2FuIEdlbSBTb2NpZXR5LCB3aGVyZSAwLjAgcmVwcmVzZW50cyBhIGZsYXdsZXNzIGRpYW1vbmQgYW5kIDEwLjAgcmVwcmVzZW50cyBhbiBpbXBlcmZlY3QgZGlhbW9uZC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBzZXF1ZW5jZSBvZiBOIGRpYW1vbmRzLCBlYWNoIHdpdGggd2VpZ2h0LCB3PHN1Yj5pPFwvc3ViPiwgaW4gY2FyYXRzIGFuZCBjbGFyaXR5LCBjPHN1Yj5pPFwvc3ViPiwgb24gdGhlIHNjYWxlIGRlc2NyaWJlZCBhYm92ZSwgZmluZCB0aGUgbG9uZ2VzdCBzdWJzZXF1ZW5jZSBvZiBkaWFtb25kcyBmb3Igd2hpY2ggdGhlIHdlaWdodCBhbmQgY2xhcml0eSBhcmUgYm90aCBiZWNvbWluZyBzdHJpY3RseSBtb3JlIGZhdm9yYWJsZSB0byBhIGJ1eWVyLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZm9sbG93aW5nIHNlcXVlbmNlIG9mIGRpYW1vbmRzLDxcL3A+XHJcblxyXG48cHJlPlxyXG53PHN1Yj5pPFwvc3ViPiAmbmJzcDtjPHN1Yj5pPFwvc3ViPlxyXG4xLjUgOS4wXHJcbjIuMCAyLjBcclxuMi41IDYuMFxyXG4zLjAgNS4wXHJcbjQuMCAyLjBcclxuMTAuMCA1LjU8XC9wcmU+XHJcblxyXG48cD50aGUgbG9uZ2VzdCBkZXNpcmFibGUgc3Vic2VxdWVuY2UgaXM8XC9wPlxyXG5cclxuPHByZT5cclxuMS41IDkuMFxyXG4yLjUgNi4wXHJcbjMuMCA1LjBcclxuNC4wIDIuMDxcL3ByZT5cclxuXHJcbjxwPmJlY2F1c2UgdGhlIHdlaWdodHMgc3RyaWN0bHkgaW5jcmVhc2Ugd2hpbGUgdGhlIGNsYXJpdGllcyBzdHJpY3RseSBkZWNyZWFzZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGJlZ2lucyB3aXRoIGEgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgVCwgMSAmbGU7IFQgJmxlOyAxMDAsIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBiZWdpbnMgd2l0aCBhIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgMjAwLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgZGlhbW9uZHMuIE5leHQgZm9sbG93IE4gbGluZXMgd2l0aCAyIHJlYWwgbnVtYmVycyB3PHN1Yj5pPFwvc3ViPiBhbmQgYzxzdWI+aTxcL3N1Yj4sIDAuMCAmbGU7IHc8c3ViPmk8XC9zdWI+LCBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwLjAsIGluZGljYXRpbmcgdGhlIHdlaWdodCBpbiBjYXJhdHMgYW5kIHRoZSBjbGFyaXR5IG9mIGRpYW1vbmQgaSwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IGRlc2lyYWJsZSBzdWJzZXF1ZW5jZSBvZiBkaWFtb25kcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > North America > Pacific Northwest Regional > 2014 Pacific Northwest Region Programming Contest > Division 2 O번