| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 142 | 67 | 61 | 53.043% |
온조는 산 오르는 것을 좋아하는 등반가이다. 그래서 온조는 길이가 $N$인 수열 $A_1, \cdots, A_N$에서 산 모양을 최대한 많이 찾으려고 한다.
만약 $A$의 부분수열 $A_l, \cdots, A_r (l \le r)$에 대해서, 어떤 정수 $l \le k \le r$가 존재하여 $A_l \le A_{l+1} \le \cdots \le A_k \ge \cdots \ge A_{r-1} \ge A_r$을 만족한다면 이 부분수열이 산 모양이라고 하자.
온조를 도와 수열 $A$가 주어지면 $A$의 부분수열 중 산 모양인 것의 개수를 구하여라.
첫째 줄에 수열 $A$의 길이 $N$이 주어진다.
둘째 줄에 $N$개의 정수 $A_1, \cdots, A_N$이 공백을 사이에 두고 주어진다.
첫째 줄에 $A$의 부분수열 중 산 모양인 것의 개수를 출력하라.
5 1 2 3 2 3
12
부분수열 $A_l, \cdots, A_r$을 $[l, r]$로 표현하자. 산 모양인 부분수열은 $[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [1, 2], [2, 3], [3, 4], [4, 5], [1, 3], [2, 4], [1, 4]$로 모두 12ドル$개이다.
3 100 100 100
6
모두 같은 수들로 이루어진 부분수열은 산 모양이므로 모든 부분수열이 산 모양이다.
7 1 1 3 3 2 2 4
24
University > 강원도 대학생 코딩 경진대회 > 2024 강원도 대학생 코딩경진대회 E번