시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB280786238.272%

문제

나코더 회원들은 재민이의 생일을 축하하기 위해, 열심히 생일 케이크를 만들고 있다.

케이크를 만들기 위해서 현재 길이 Wi, 높이 1인 빵조각이 1 ~ N 순서대로 만들어지고 있다. 나코더 회원들은 이 빵조각들을 모두 쌓아서 (버리면 안 된다) 층층이 케이크를 만들고자 한다.

케이크는 여러 층으로 구성될 수 있는데, 한 층의 길이는 그 층에 있는 빵조각의 길이의 합이며, 위에 있는 층의 길이가 아래에 있는 층의 길이보다 클 수 없다. (그러면, 케익이 무너지고 말 것이다!)

또한, 나중에 만들어진 빵조각은 전에 만들어진 빵조각보다 낮은 층에 올라갈 수 없다.

이를 만족하는 선에서 최대한의 높이로 케익을 쌓고자 할때, 과연 몇층까지 쌓을 수 있을까?

입력

첫 번째 줄에 N이 주어진다. (1 <= N <= 100000)

이후 N개의 줄에 Wi가 주어진다 (1 <= Wi <= 10000)

출력

가장 높은 케이크의 크기를 출력하라.

예제 입력 1

3
1
2
3

예제 출력 1

2

힌트

다음과 같은 구성이 가능하다.

 +----------+
 |    3     | 
 +---+------+ 
 | 1 |   2  | 
 +---+------+
W3sicHJvYmxlbV9pZCI6IjYxMTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmMDBcdWM3NzRcdWQwNmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjA5OFx1Y2Y1NFx1YjM1NCBcdWQ2OGNcdWM2ZDBcdWI0ZTRcdWM3NDAgXHVjN2FjXHViYmZjXHVjNzc0XHVjNzU4IFx1YzBkZFx1Yzc3Y1x1Yzc0NCBcdWNkOTVcdWQ1NThcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVjMGRkXHVjNzdjIFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmMDBcdWM3NzRcdWQwNmNcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ2MDRcdWM3YWMgXHVhZTM4XHVjNzc0IFdpLCBcdWIxOTJcdWM3NzQgMVx1Yzc3OCBcdWJlNzVcdWM4NzBcdWFjMDFcdWM3NzQgMSB+IE4gXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjA5OFx1Y2Y1NFx1YjM1NCBcdWQ2OGNcdWM2ZDBcdWI0ZTRcdWM3NDAgXHVjNzc0IFx1YmU3NVx1Yzg3MFx1YWMwMVx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMzEzXHVjNTQ0XHVjMTFjIChcdWJjODRcdWI5YWNcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNCkgXHVjZTM1XHVjZTM1XHVjNzc0IFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmMDBcdWM3NzRcdWQwNmNcdWIyOTQgXHVjNWVjXHViN2VjIFx1Y2UzNVx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVkNTVjIFx1Y2UzNVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhZGY4IFx1Y2UzNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHViZTc1XHVjODcwXHVhYzAxXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NzRcdWJhNzAsIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZTM1XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Y2UzNVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHVkMDc0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIChcdWFkZjhcdWI3ZWNcdWJhNzQsIFx1Y2YwMFx1Yzc3NVx1Yzc3NCBcdWJiMzRcdWIxMDhcdWM5YzBcdWFjZTAgXHViOWQwIFx1YWM4M1x1Yzc3NFx1YjJlNCEpPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgXHViMDk4XHVjOTExXHVjNWQwIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWJlNzVcdWM4NzBcdWFjMDFcdWM3NDAgXHVjODA0XHVjNWQwIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWJlNzVcdWM4NzBcdWFjMDFcdWJjZjRcdWIyZTQgXHViMGFlXHVjNzQwIFx1Y2UzNVx1YzVkMCBcdWM2MmNcdWI3N2NcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMxMjBcdWM1ZDBcdWMxMWMgXHVjZDVjXHViMzAwXHVkNTVjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjg1YyBcdWNmMDBcdWM3NzVcdWM3NDQgXHVjMzEzXHVhY2UwXHVjNzkwIFx1ZDU2MFx1YjU0YywgXHVhY2ZjXHVjNWYwIFx1YmE4N1x1Y2UzNVx1YWU0Y1x1YzljMCBcdWMzMTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7PSBOICZsdDs9IDEwMDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFdpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMSAmbHQ7PSBXaSAmbHQ7PSAxMDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWQ2Y1x1YzEzMVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiArLS0tLS0tLS0tLStcclxuIHwgICAgMyAgICAgfCBcclxuICstLS0rLS0tLS0tKyBcclxuIHwgMSB8ICAgMiAgfCBcclxuICstLS0rLS0tLS0tK1xyXG48XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNjExNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRvd2VyIG9mIEhheSIsImRlc2NyaXB0aW9uIjoiPHA+Q293cyBzbyBoYXRlIHRoZSBkYXJrLiBJbiBvcmRlciB0byBjaGFuZ2UgYSBsaWdodGJ1bGIgYXQgdGhlIHRvcCBvZiB0aGUgYmFybiwgQmVzc2llIG11c3QgYnVpbGQgYSB0b3dlciBvdXQgb2YgYmFsZXMgb2YgaGF5IHRvIGNsaW1iIHNvIHRoYXQgc2hlIGNhbiByZWFjaCBpdC4gVGhlIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDAsMDAwKSBiYWxlcyBvZiBoYXkgKGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OKSBlbnRlciB0aGUgYmFybiBzZXF1ZW50aWFsbHkgb24gYSBjb252ZXlvciBiZWx0LiBCYWxlIGkgaGFzIGludGVnZXIgd2lkdGggd19pICgxICZsdDs9IHdfaSAmbHQ7PSAxMCwwMDApOyBhbGwgYmFsZXMgaGF2ZSBkZXB0aCBhbmQgaGVpZ2h0IG9mIG9uZSB1bml0LjxcL3A+XHJcblxyXG48cD5CZXNzaWUgbXVzdCB1c2UgYWxsIE4gaGF5IGJhbGVzIHRvIGJ1aWxkIHRoZSB0b3dlciBhbmQgbXVzdCBsYXkgdGhlbSBkb3duIGluIHRoZSBvcmRlciB0aGV5IGFycml2ZS4gU2hlIGNhbiBsYXkgYXMgbWFueSBiYWxlcyBhcyBzaGUgd2lzaGVzICh0aWdodGx5IHBhY2tlZCBpbiBhIGxpbmUsIG9mIGNvdXJzZSkgdG8gY3JlYXRlIHRoZSBmb3VuZGF0aW9uIG9mIHRoZSB0b3dlci4gU2hlIGNhbiB0aGVuIGxheSBzb21lIG9mIHRoZSBuZXh0IGJhbGVzIG9uIHRvcCBvZiB0aGUgcHJldmlvdXMgbGV2ZWwgdG8gY3JlYXRlIHRoZSBuZXh0IGxldmVsIChubyBsZXZlbCBjYW4gYmUgd2lkZXIgdGhhbiB0aGUgbGV2ZWwgYmVuZWF0aCBpdCkuIFNoZSBjb250aW51ZXMgdGhpcyBwcm9jZXNzIHVudGlsIGFsbCB0aGUgYmFsZXMgYXJlIHVzZWQuIFNoZSBtdXN0IHN0YWNrIHRoZSBiYWxlcyBpbiB0aGUgb3JkZXIgdGhleSBhcnJpdmUsIGZyb20gdGhlIGJvdHRvbSB0byB0aGUgdG9wIG9mIHRoZSB0b3dlci4gVG8gYmUgY2xlYXI6IHNoZSBtdXN0IG5vdCB0cnkgdG8gc25lYWsgYSBiYWxlIGJhY2sgb24gdGhlIGZvdW5kYXRpb24gYWZ0ZXIgYSBiYWxlIGlzIHBsYWNlZCBvbiB0aGUgc2Vjb25kIGxheWVyLjxcL3A+XHJcblxyXG48cD5CZXNzaWUmIzM5O3MgZ29hbCBpcyB0byBjcmVhdGUgdGhlIHRhbGxlc3QgdG93ZXIgcG9zc2libGUgLS0gYW5kIHNoZSBhbHJlYWR5IGtub3dzIGhvdyB3aWRlIGVhY2ggZXZlcnkgYmFsZSBvZiBoYXkgd2lsbCBiZSBhcyBpdCBjb21lcyBpbnRvIHRoZSBiYXJuIG9uIHRoZSBiZWx0LiBIb3cgdGFsbCBhIHRvd2VyIGNhbiBzaGUgY29uc3RydWN0PzxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyOiB3X2k8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciwgdGhlIGhlaWdodCBvZiB0aGUgdGFsbGVzdCBwb3NzaWJsZSB0b3dlciB0aGF0IGNhbiBiZSBidWlsdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5Vc2UgdGhlIGZpcnN0IGJhbGVzIHdpdGggd2lkdGggMSBhbmQgMiBmb3IgdGhlIGJvdHRvbSByb3cgKHRvdGFsIHdpZHRoOiAzKSwgdGhlbiB0aGUgbmV4dCBiYWxlICh3aWR0aCAzKSBmb3IgdGhlIHRvcCByb3c6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICstLS0tLS0tLS0tK1xyXG4gICAgICAgICAgICB8ICAgIDMgICAgIHxcclxuICAgICAgICAgICAgKy0tLSstLS0tLS0rXHJcbiAgICAgICAgICAgIHwgMSB8ICAgMiAgfFxyXG4gICAgICAgICAgICArLS0tKy0tLS0tLSs8XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO US Open 2009 Contest > Gold 3번

  • 문제를 번역한 사람: koosaga