TLE '16 Contest 4 P1 - Stack of Presents - DMOJ: Modern Online Judge

TLE '16 Contest 4 P1 - Stack of Presents

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

ZQFMGB12

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$ ~N~ presents that he could possibly give to the girl. The $i^\text{th}$ ~i^\text{th}~ present has a weight of $w_i$ ~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$ ~N~ $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~.

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

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

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

Output Specification

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

Sample Input

Sample Output

Explanation for Sample Output

The CS Nerd can stack presents in the order $2$ ~2~, $4$ ~4~, and $3$ ~3~ from the bottom. The weights of these presents are $8$ ~8~, $5$ ~5~, and $2$ ~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.