레이팅 미적용농부 존은 한 줄로 놓인 \(N\) (\(1\le N\le 2\cdot 10^5\))개의 잔디밭 구역을 가지고 있다. 구역 \(i\)의 박테리아 수치는 건강한 잔디의 수치와 \(a_i\)만큼 차이가 난다 (\(-10^{15}\le a_i \le 10^{15}\)). 예를 들어 \(a_i = -3\)이면 구역 \(i\)의 박테리아 수치는 정상보다 3만큼 낮아서, 건강하다고 간주되려면 정확히 3단위의 박테리아가 추가로 필요하다.
농부 존은 모든 잔디밭 구역의 박테리아 수치를 건강한 수준으로 맞추고 싶다. 마침 그는 밭에 뿌릴 수 있는 두 종류의 살포제를 가지고 있는데, 하나는 박테리아를 추가하고 다른 하나는 박테리아를 제거한다. 어느 살포제든 뿌릴 때 농부 존은 구역 \(N\) (가장 오른쪽 구역)에 서서 분무기의 파워 레벨 \(L\)을 선택한다 (\(1 \leq L \leq N\)).
분무기는 농부 존과 가까운 구역에 가장 큰 영향을 주고, 멀어질수록 효과가 줄어든다. 농부 존이 박테리아를 추가하는 살포제를 선택하면 구역 \(N\)에 \(L\)단위, 구역 \(N-1\)에 \(L-1\)단위, 구역 \(N-2\)에 \(L-2\)단위의 박테리아가 추가되는 식이다. 구역 \(1 \ldots N-L\)은 분무기의 레벨이 닿을 만큼 강하지 않으므로 박테리아를 받지 않는다. 마찬가지로 박테리아를 제거하는 살포제를 선택하면 구역 \(N\)에서 \(L\)단위, 구역 \(N-1\)에서 \(L-1\)단위가 제거되는 식이다. 이때도 구역 \(1 \ldots N-L\)은 영향을 받지 않는다.
모든 잔디밭 구역이 건강한 잔디의 권장 박테리아 수치를 갖도록 하기 위해 농부 존이 분무기를 사용해야 하는 최소 횟수를 구하여라. 답이 \(10^9\) 이하임이 보장된다.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의하라.
출제: Rohin Garg
배점
- 입력 3-5: \(N \le 10^3\), 답은 최대 \(10^3\)
- 입력 6-10: \(N \le 10^3\)
- 입력 11-15: 추가 제약 없음.
출제: Rohin Garg
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 각 잔디밭 구역의 초기 박테리아 수치인 \(N\)개의 정수 \(a_1\dots a_N\)이 주어진다.
모든 잔디밭 구역이 건강한 잔디의 권장 박테리아 수치를 갖도록 하는 데 필요한 최소 살포 횟수를 출력한다.
2
-1 36Use the type of pesticide that removes bacteria, at a power level of 1, five
times. Then use the type of pesticide that adds bacteria, with a power level of
\(2\), one time.
5
1 3 -2 -7 526riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Bronze