레이팅 미적용*참고: 이 문제의 시간 제한은 기본값의 1.5배인 3초이다.*
길이 \(N\)의 정수 배열 \(a_1,a_2,\dots,a_N\)(\(2\le N\le 10^6, 1\le a_i\le N\))이 주어진다. \(a\)의 \(N(N+1)/2\)개의 모든 연속 부분 배열에 대해 아래 부분 문제의 답을 모두 더한 값을 출력하시오.
비어 있지 않은 정수 리스트가 주어지면, 리스트의 크기가 정확히 1이 될 때까지 다음 연산을 번갈아 수행한다(첫 번째 연산부터 시작).
- 리스트에서 연속한 두 정수를 그 최솟값으로 바꾼다.
- 리스트에서 연속한 두 정수를 그 최댓값으로 바꾼다.
마지막에 남는 정수의 최댓값을 구한다.
예를 들어,
[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]
첫 번째 배열에서는 \((10, 3)\)이 \(\min(10, 3)=3\)으로, \((4, 3)\)이 \(\max(4, 3)=4\)로 바뀐다.
Problem credits: Benjamin Qi
배점
- 입력 4-5: \(N\le 100\)
- 입력 6-7: \(N\le 5000\)
- 입력 8-9: \(\max(a)\le 10\)
- 입력 10-13: 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(a_1,a_2,\dots,a_N\)이 주어진다.
모든 부분 배열에 대한 부분 문제의 답의 합을 출력한다.
2
2 14The answer for \([2]\) is \(2\), the answer for \([1]\) is \(1\), and the answer for
\([2, 1]\) is \(1\).
Thus, our output should be \(2+1+1 = 4\).
3
3 1 3124
2 4 1 322Consider the subarray \([2, 4, 1, 3]\).
- Applying the first operation on (1, 3), our new array is \([2, 4, 1]\).
- Applying the second operation on (4, 1), our new array is \([2, 4]\).
- Applying the third operation on (2, 4), our final number is \(2\).
It can be proven that \(2\) is the maximum possible value of the final number.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Platinum