TLE '16 Contest 4 P1 - Stack of Presents

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
A stack of presents.

The CS Nerd is dreaming about giving Christmas presents to the girl. Unfortunately, he does not have enough courage to do this in real life.

In the dream, there are N presents that he could possibly give to the girl. The i^\text{th} present has a weight of w_i. The CS Nerd wants to impress the girl by building a large stack of presents – that is, presents stacked one on top of each other – and giving it to her.

However, the CS Nerd needs to ensure that the sum of the weights of the presents above any present does not exceed that present's weight. What is the maximum number of presents that can be in the stack?

Input Specification

The first line of input will contain a single integer N (1 \le N \le 100\,000).

N lines of input follow. The i^\text{th} line will consist of a single integer, w_i (1 \le w_i \le 10^9).

For 20% of the points, N \le 10.

For an additional 30% of the points, N \le 1\,000.

Output Specification

Output a single integer, the maximum possible number of presents that can be in the stack.

Sample Input

5
7
8
2
5
10

Sample Output

3

Explanation for Sample Output

The CS Nerd can stack presents in the order 2, 4, and 3 from the bottom. The weights of these presents are 8, 5, and 2, respectively. Note that this is not the only possible solution.


Comments


  • 1
    TheCool1James  commented on Dec. 24, 2016, 1:44 p.m.

    If the weights of the presents on top the stack is equal to the weight on the bottom, does it count as a valid stack?


    • 4
      ZQFMGB12  commented on Dec. 24, 2016, 2:24 p.m.

      Yes


  • 1
    md_muntaz  commented on Dec. 23, 2016, 5:27 p.m. edited

    However, the CS Nerd needs to ensure that the sum of the weights of the presents above any present does not exceed that present's weight. What is the maximum number of presents that can be in the stack?

    I can't understand this statement.


    • 5
      ZQFMGB12  commented on Dec. 23, 2016, 5:30 p.m.

      The sum of the weights of the presents on top of the current present in consideration cannot exceed the weight of the current present.