레이팅 미적용설명
비가 올 때마다 농부 존(Farmer John)의 들판은 항상 물에 잠기고 만다. 하지만 들판이 완전히 평평하지는 않아서 물이 고르지 않게 차오르고, 그 결과 물줄기로 분리된 여러 개의 "섬"이 생긴다.
FJ의 들판은 N개 (1 <= N <= 100,000)의 연속한 높이 값 H(1)...H(n)으로 명시되는 1차원 지형으로 표현된다. 지형이 사실상 무한한 높이의 높은 울타리로 둘러싸여 있다고 가정하고, 폭풍우가 칠 때 무슨 일이 일어나는지 생각해 보자. 가장 낮은 지역이 먼저 물에 잠기면서 여러 개의 분리된 "섬"이 생기고, 물이 계속 차오르면 결국 모두 잠기게 된다. 수위가 어떤 땅의 높이와 같아지는 순간, 그 땅은 물에 잠긴 것으로 간주한다.
물이 들판 전체가 잠기는 지점까지 차오르는 동안, 폭풍우 중 어느 한 시점에 볼 수 있는 섬의 최대 개수를 계산하시오. (이 문제의 그림은 생략되었다.)
제약
입력 형식
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 높이 H(i)가 주어진다. (1 <= H(i) <= 1,000,000,000)
출력 형식
폭풍우가 진행되는 동안 어느 한 시점에 나타나는 섬의 최대 개수를 나타내는 정수 하나.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
islands.in · 출력을 쓸 파일 islands.out예제 1
입력
8
3
5
2
3
1
4
2
3출력
4문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > US Open > Bronze
태그