Min Max Subarrays
다이아몬드 V의견: 0
*Note: The time limit for this problem is 3s, 1.5x the default.*
You are given a length-\(N\) integer array \(a_1,a_2,\dots,a_N\)
(\(2\le N\le 10^6, 1\le a_i\le N\)). Output the sum of the answers for the
subproblem below over all \(N(N+1)/2\) contiguous subarrays of \(a\).
Given a nonempty list of integers, alternate the following operations (starting
with the first operation) until the list has size exactly one.
- Replace two consecutive integers in the list with their minimum.
- Replace two consecutive integers in the list with their maximum.
Determine the maximum possible value of the final remaining integer.
For example,
[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]
In the first array, \((10, 3)\) is replaced by \(\min(10, 3)=3\) and \((4, 3)\) is
replaced by \(\max(4, 3)=4\).
Problem credits: Benjamin Qi
SCORING
- Inputs 4-5: \(N\le 100\)
- Inputs 6-7: \(N\le 5000\)
- Inputs 8-9: \(\max(a)\le 10\)
- Inputs 10-13: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\).
The second line contains \(a_1,a_2,\dots,a_N\).
The sum of the answer to the subproblem over all subarrays.
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
평가 및 의견
Min Max Subarrays
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Min Max Subarrays