oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

flappybird Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

flappybird.html

Problem Description

A fire has broken out in a large tower with N floors, and there is a person stuck at each floor trying to get out. Feeling his internal sense of justice raging, Rar the Cat took to his helicopter and flew up to the top of the tower to attempt to save the people in the tower. When he got to the top of the tower, he found an empty lift shaft that was blown out by the fire. Peering into the lift shaft, he found that everyone was still busy playing Flappy Bird!

Wait what... a high score of 145? How could this be? How could anyone beat the mighty Rar the Cat? Fury raged inside Rar the Cat. Conflicted between the urge for revenge and the rivalry between his Flappy Bird foes, he comes out with a new plan. To save the people in the building, Rar the Cat will throw lift cars down the lift shaft to pick the people up. Since there is no electricity, the lift cars can only go downwards from floor N to the ground floor, where the people are supposed to get to. To execute his brilliant revenge plan, a lift car can only pick up a person at a certain floor if all the people currently in the lift car has a Flappy Bird high score higher than the person currently entering it.

Given a list of the Flappy Bird high scores of each of the people on each floor, find out the minimum number of lift cars Rar the Cat has to throw down to get everyone down to the ground floor.

Input

The first line of input will contain one integer, N.
The second line of input will contain N integers, with the ith integer representing the Flappy Bird high score of the person on floor i.

Output

Your output should contain one integer, the minimum number of lift cars Rar the Cat has to throw down to get everyone down to the ground floor.

Limits

All Flappy Bird high scores will be less than 231-1.
Subtask 1 (14%): 1 ≤ N ≤ 10. In addition, all Flappy Bird high scores will be less than or equal to 10.
Subtask 2 (28%): 1 ≤ N ≤ 1000.
Subtask 3 (58%): 1 ≤ N ≤ 1000000.
Subtask 4 (0%): As per sample testcases.

Sample Input 1

5
1 2 3 3 5

Sample Output 1

2

Sample Input 2

5
5 4 2 5 1

Sample Output 2

4

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
114201s32MBMinimum
228401s32MBMinimum
358601s32MBMinimum
4021s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o flappybird -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.