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

pyramidhotel Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

statement.html

Problem Description

After doing setsquare, Guan has acquired a new brilliant plan :D

On a street with N grids, where each grid has a height limit Hi, Guan wishes to erect a half-pyramid hotel

The half-pyramid hotel must face right (i.e. from left to right the height of the hotel will be strictly decreasing)

The heights of the buildings constituting the hotel must be a sequence of consecutive numbers, with the smallest consecutive number being 1

I.e. from left to right, 3,2,1 or 4,3,2,1 or 6,5,4,3,2,1

Guan wants to find out the maximum height of the largest possible pyramid hotel he can erect. Help him

Input

The first line contains the number of city grids, N

The next N lines contain the height limit of each grid, Hi, from left to right

Constraints

1<=Hi<=1,000,000

1<=N<=1,000,000

Output

A single number, the maximum height of the largest possible pyramid hotel Guan can erect

Subtasks

Subtask 1 (3%) Hi=N-i (i starts from 1 and ends with N)

Subtask 2 (23%) N<=1,000

Subtask 3 (74%) N<=1,000,000

Warning

Please use scanf/printf or put the line ios_base::sync_with_stdio(false) if using cin/cout (And avoid using scanf/printf), or you will TLE

Sample Testcase 1

Input

6
6 5 4 3 2 1
Output
6

Explanation

Guan builds a hotel from the leftmost grid of heights 6,5,4,3,2,1

Sample Testcase 2

Input

6
1 2 3 4 5 6
Output
3

Explanation

Guan builds a hotel of 3,2,1 on the tiles with a height limit of 3,4,5 respectively

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
13100.5s64MBMinimum
223110.5s64MBMinimum
374110.5s64MBMinimum
4020.5s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o pyramidhotel -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.