RiseOJ – 조경 공사

설명

농부 존은 아름답게 조경된 정원을 만들고 있으며, 그 과정에서 많은 양의 흙을 옮겨야 한다.

정원은 $$N$$ 개의 화단이 일렬로 늘어선 형태이며( $1 \leq N \leq 100,000$ ), 화단 $$i$$ 에는 처음에 $$A_i$$ 단위의 흙이 있다. 농부 존은 정원을 다시 조경하여 각 화단 $$i$$ 에 대신 $$B_i$$ 단위의 흙이 있도록 만들고 싶다. $$A_i$$ 와 $$B_i$$ 는 모두 $0 \ldots 10$ 범위의 정수이다.

정원을 조경하기 위해 농부 존에게는 몇 가지 선택지가 있다. $$X$$ 단위의 돈을 내고 흙 한 단위를 사서 원하는 화단에 놓을 수 있다. $$Y$$ 단위의 돈을 내고 원하는 화단에서 흙 한 단위를 제거해 실어 보낼 수 있다. 또한 화단 $$i$$ 에서 화단 $$j$$ 로 흙 한 단위를 옮길 수 있으며, 이때 비용은 $$Z$$ 곱하기 $$|i-j|$$ 이다. 농부 존이 조경 공사를 완료하는 데 필요한 최소 총비용을 계산하시오.

문제 출제: 브라이언 딘(Brian Dean)

제약

문제 출제: 브라이언 딘(Brian Dean)

입력 형식

입력의 첫째 줄에 $$N$$ , $$X$$ , $$Y$$ , $$Z$$ ( $0 \leq X, Y \le 10^8; 0 \le Z \leq 1000$ )가 주어진다. $$i+1$$ 번째 줄에는 정수 $$A_i$$ 와 $$B_i$$ 가 주어진다.

출력 형식

농부 존이 조경에 써야 하는 최소 총비용을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 landscape.in · 출력을 쓸 파일 landscape.out

예제 1

입력

4 100 200 1
1 4
2 3
3 2
4 0

출력

설명

Note that this problem has been asked in a previous USACO contest,
at the silver level; however, the limits in the present version have
been raised considerably, so one should not expect many points from
the solution to the previous, easier version.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > US Open > Platinum

올림피아드 > USACO > 2015-2016 > US Open > Platinum

태그

JudgeUSACO

조경 공사

평가 및 의견

풀이 제출