레이팅 미적용농부 존의 소 \(N\)마리는 축사의 실내 온도에 매우 민감하다. 어떤 소는 시원한 온도를 좋아하고, 어떤 소는 따뜻한 온도를 선호한다.
농부 존의 축사에는 \(1 \ldots N\)으로 번호가 붙은 \(N\)개의 우리가 일렬로 있고, 각 우리에는 소가 한 마리씩 있다. \(i\)번째 소는 자기 우리의 온도가 \(p_i\)이기를 원하는데, 현재 그 우리의 온도는 \(t_i\)이다. 모든 소가 쾌적하게 지낼 수 있도록, 농부 존은 다소 흥미로운 방식으로 제어되는 새 에어컨 시스템을 설치한다. 그는 시스템에 연속한 우리 구간의 온도를 1만큼 올리거나 내리라는 명령을 보낼 수 있다. 예를 들어 "우리 \(5 \ldots 8\)의 온도를 1만큼 올려라"와 같은 식이다. 구간은 우리 하나만큼 짧을 수도 있다.
모든 소의 우리가 그 우리에 사는 소에게 이상적인 온도가 되도록 하기 위해, 농부 존이 새 에어컨 시스템에 보내야 하는 명령의 최소 개수를 구하는 것을 도와주자.
출제자: Brian Dean
채점 방식
- 테스트 케이스 2-5는 \(N \leq 100\)을 만족한다.
- 테스트 케이스 6-8은 \(N \leq 1000\)을 만족한다.
- 테스트 케이스 9-10은 \(N \leq 100,000\)을 만족한다.
- 테스트 케이스 1-6과 9에서 온도 값은 최대 \(100\)이다.
- 테스트 케이스 7-8과 10에서 온도 값은 최대 \(10,000\)이다.
출제자: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 줄에 공백으로 구분된 \(N\)개의 음이 아닌 정수 \(p_1 \ldots p_N\)이 주어진다. 마지막 줄에 \(N\)개의 음이 아닌 정수 \(t_1 \ldots t_N\)이 주어진다.
농부 존이 사용해야 하는 명령의 최소 개수를 하나의 정수로 출력한다.
5
1 5 3 3 4
1 2 2 2 15One optimal set of commands Farmer John can use might be the following:
Initial temperatures: 1 2 2 2 1
Increase stalls 2..5: 1 3 3 3 2
Increase stalls 2..5: 1 4 4 4 3
Increase stalls 2..5: 1 5 5 5 4
Decrease stalls 3..4: 1 5 4 4 4
Decrease stalls 3..4: 1 5 3 3 4
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Bronze