| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 348 | 141 | 120 | 43.165% |
건구스는 축제의 마무리를 장식하기 위해 하늘로 무한히 상승하는 $N$개의 등불을 준비했다. 등불은 왼쪽부터 차례대로 $1$번부터 번호가 매겨져 있으며, $i$번 등불은 매초 높이가 $A_i$만큼 상승한다. 처음에는 모든 등불을 높이 $0$에 준비해 두었다. 건구스는 축제가 끝날 때, 연속하는 $S$개의 등불을 골라 $1$초 간격으로 번호가 작은 것부터 날려 보내려고 한다.
사람들은 하나의 등불이 다른 등불들을 앞지르면, 앞지르는 등불의 개수만큼 소원을 빈다. 건구스는 사람들이 최대한 많은 소원을 빌도록 날려 보낼 등불을 고르려고 한다. $S$개의 연속하는 등불을 적절히 골라 날려 보냈을 때, 사람들은 최대 몇 개의 소원을 빌 수 있을까?
첫째 줄에 건구스가 준비한 등불의 개수 $N$과 날려 보낼 등불의 개수 $S$가 공백으로 구분되어 주어진다. $\left( 2\leq N\leq 100\, 000;\ 1\leq S\leq N \right)$
둘째 줄에 각 등불이 매초 상승하는 정도를 나타내는 $N$개의 정수 $A_i$가 순서대로 공백으로 구분되어 주어진다. $\left( 1\leq A_i\leq 10^{9} \right)$
사람들이 최대한 많은 소원을 빌도록 날려 보낼 등불들을 골랐을 때, 소원을 비는 횟수를 출력한다.
4 4 1 3 7 1
3
각각 높이가 매초 $1,3,7,1$만큼 상승하는 등불을 골랐다고 하자. 처음 등불들의 높이는 $0,0,0,0$이다.
더 이상 하나의 등불이 다른 등불을 앞지르는 경우는 없기에 사람들은 각각 $2$초에서 $1$번, $3$초에서 $2$번 총 $3$번 소원을 빈다.
5 3 10 17 19 7 10
3
10 10 1 2 3 4 5 6 7 8 9 10
45
10 9 1 2 3 4 5 6 7 8 9 10
36
University > 건국대학교 > 2023 건국대학교 프로그래밍 경진대회 (KUPC) > Division 1 H번
University > 건국대학교 > 2023 건국대학교 프로그래밍 경진대회 (KUPC) > Open Contest L번