시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 280 | 78 | 62 | 38.272% |
나코더 회원들은 재민이의 생일을 축하하기 위해, 열심히 생일 케이크를 만들고 있다.
케이크를 만들기 위해서 현재 길이 Wi, 높이 1인 빵조각이 1 ~ N 순서대로 만들어지고 있다. 나코더 회원들은 이 빵조각들을 모두 쌓아서 (버리면 안 된다) 층층이 케이크를 만들고자 한다.
케이크는 여러 층으로 구성될 수 있는데, 한 층의 길이는 그 층에 있는 빵조각의 길이의 합이며, 위에 있는 층의 길이가 아래에 있는 층의 길이보다 클 수 없다. (그러면, 케익이 무너지고 말 것이다!)
또한, 나중에 만들어진 빵조각은 전에 만들어진 빵조각보다 낮은 층에 올라갈 수 없다.
이를 만족하는 선에서 최대한의 높이로 케익을 쌓고자 할때, 과연 몇층까지 쌓을 수 있을까?
첫 번째 줄에 N이 주어진다. (1 <= N <= 100000)
이후 N개의 줄에 Wi가 주어진다 (1 <= Wi <= 10000)
가장 높은 케이크의 크기를 출력하라.
3 1 2 3
2
다음과 같은 구성이 가능하다.
+----------+ | 3 | +---+------+ | 1 | 2 | +---+------+
Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO US Open 2009 Contest > Gold 3번