Mock CCO '17 Day 1 P1 - Fast Fuhrer Transform

View as PDF

Submit solution

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

Author:
Problem type

Imaxblue has travellled back in time to kill Fuhrer Bradley. Unfortunately, this plan involves infiltrating the Amestris government. This means that he must bribe purchase legal government security cards. There are N security levels in the Amestris government, numbered 0 to N-1. There is a new security card available for purchase at each level, and you can purchase cards at lower levels as well. Initially, Imaxblue has a security level of 0, and his total security level is equal to the sum of his cards. Imaxblue would like to raise as little suspicion as possible, by purchasing the most amount of cards before going past the N-1th security level. In addition, each card he purchases must have a higher security number than the previous one purchased. Print -1 if it is impossible.

Subtasks

For all cases, N \le 200\,000
For 5 of the 25 points, N \le 4\,000

Input Specification

On the first line: N On the second line: N integers, representing the security cards available for purchase on the i-th day

Sample Input

9
1 2 5 4 2 3 10 1 1

Sample Output

4

Explanation for Sample Output

First, purchase the card of value 1, raising your security level to 1.
Then, purchase the card of value 2, raising your level to 3.
Then, purchase the card of value 4, raising your level to 7.
Then, purchase the card of value 5, raising your level to 12.

Note: you cannot purchase the second card of value 2 or the card of value 3, since the cards you purchase must be strictly increasing.


Comments


  • 0
    DarthVader336  commented on April 12, 2018, 10:26 a.m.

    Why cannot imaxblue buy the card of value 10?


    • 1
      aeternalis1  commented on April 12, 2018, 10:37 a.m.

      Upon purchasing the card of value 5, he'd already surpassed the N-1th security level, and so he couldn't buy any more past that point. It would have been another valid solution to buy the card of value 10 in place of the card of value 5.


      • 0
        DarthVader336  commented on April 13, 2018, 12:06 a.m.

        Is it because his security value can beat any of the security cards at every level? (12>10, 12>2 ....)


      • 0
        DarthVader336  commented on April 13, 2018, 12:05 a.m.

        How have he surpassed the N-1th security level?


        • 2
          Roynaruto  commented on April 13, 2018, 8:21 a.m.

          For help, I recommend you join DMOJ's Slack to prevent spamming on comments.