레이팅 미적용베시는 휴대폰에 게임을 내려받아 즐기는 것을 좋아한다. 커다란 발굽으로 작은 터치스크린을 조작하기가 꽤 번거롭기는 하지만 말이다.
베시는 지금 하고 있는 게임에 특히 푹 빠져 있다. 게임은 \(N\)개의 양의 정수로 이루어진 수열 \(a_1,a_2,\ldots,a_N\) (\(2\le N\le 262,144\))으로 시작하며, 각 수는 \(1\ldots 10^6\) 범위에 있다. 한 번의 이동에서 베시는 인접한 두 수를 골라, 두 수의 최댓값보다 1 큰 하나의 수로 교체할 수 있다(예를 들어 인접한 쌍 \((5,7)\)을 \(8\)로 교체할 수 있다). 게임은 \(N-1\)번의 이동 후에 끝나며, 이때 수는 하나만 남는다. 목표는 이 마지막 수를 최소화하는 것이다.
베시는 이 게임이 당신에게 너무 쉽다는 것을 알고 있다. 그래서 당신의 임무는 \(a\)에 대해서만 최적으로 게임을 하는 것이 아니라, \(a\)의 모든 연속 부분 수열에 대해 게임을 하는 것이다.
\(a\)의 \(\frac{N(N+1)}{2}\)개의 모든 연속 부분 수열에 대해, 가능한 최소 최종 수의 합을 출력한다.
출제: Benjamin Qi
배점
- 테스트 케이스 2-3은 \(N\le 300\)을 만족한다.
- 테스트 케이스 4-5는 \(N\le 3000\)을 만족한다.
- 테스트 케이스 6-8에서는 모든 값이 \(40\) 이하이다.
- 테스트 케이스 9-11에서는 입력 수열이 비내림차순이다.
- 테스트 케이스 12-23은 추가 제약이 없다.
출제: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 줄에 입력 수열을 나타내는 \(N\)개의 정수가 공백으로 구분되어 주어진다.
합을 한 줄에 출력한다.
6
1 3 1 2 1 10115There are \(\frac{6\cdot 7}{2}=21\) contiguous subsequences in total. For example,
the minimum possible final number for the contiguous subsequence \([1,3,1,2,1]\)
is \(5\), which can be obtained via the following sequence of operations:
original -> [1,3,1,2,1]
combine 1&3 -> [4,1,2,1]
combine 2&1 -> [4,1,3]
combine 1&3 -> [4,4]
combine 4&4 -> [5]
Here are the minimum possible final numbers for each contiguous subsequence:
final(1:1) = 1
final(1:2) = 4
final(1:3) = 5
final(1:4) = 5
final(1:5) = 5
final(1:6) = 11
final(2:2) = 3
final(2:3) = 4
final(2:4) = 4
final(2:5) = 5
final(2:6) = 11
final(3:3) = 1
final(3:4) = 3
final(3:5) = 4
final(3:6) = 11
final(4:4) = 2
final(4:5) = 3
final(4:6) = 11
final(5:5) = 1
final(5:6) = 11
final(6:6) = 10
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Platinum