RiseOJ – 휴게소

설명

농부 존과 그의 개인 트레이너 베시가 밴카우버 산을 오르고 있다. 그들에게(그리고 여러분에게) 이 산은 길이 $$L$$ 미터( $1 \leq L \leq 10^6$ )의 길고 곧은 등산로로 나타낼 수 있다. 농부 존은 미터당 $$r_F$$ 초( $1 \leq r_F \leq 10^6$ )의 일정한 속도로 등산로를 오를 것이다. 그는 지구력을 단련하는 중이므로 도중에 전혀 쉬지 않을 것이다.

하지만 베시는 휴게소에서 쉬는 것이 허용되며, 그곳에서 맛있는 풀을 발견할 수도 있다. 물론 아무 데서나 멈출 수는 없다! 등산로에는 $$N$$ 개의 휴게소가 있다 ( $1 \leq N \leq 10^5$ ). $$i$$ 번째 휴게소는 등산로 시작점에서 $$x_i$$ 미터 떨어진 곳에 있고 ( $$0 < x_i < L$$ ), 맛있음 값 $$c_i$$ 를 가진다 ( $1 \leq c_i \leq 10^6$ ). 베시가 휴게소 $$i$$ 에서 $$t$$ 초 동안 쉬면, $c_i \cdot t$ 단위의 맛있음을 얻는다.

휴게소에 있지 않을 때 베시는 미터당 $$r_B$$ 초( $1 \leq r_B \leq 10^6$ )의 고정된 속도로 등산한다. 베시는 젊고 건강하므로 $$r_B$$ 는 $$r_F$$ 보다 엄격히 작다.

베시는 맛있는 풀 섭취량을 최대화하고 싶다. 하지만 그녀는 농부 존이 걱정된다. 등산 도중 어느 순간이라도 자신이 등산로에서 농부 존보다 뒤에 있게 되면, 그가 계속할 의욕을 완전히 잃어버릴지도 모른다고 생각하기 때문이다!

농부 존이 등산을 완주하도록 보장하면서 베시가 얻을 수 있는 최대 총 맛있음 단위를 구하도록 도와주자.

출제자: Dhruv Rohatgi

제약

출제자: Dhruv Rohatgi

입력 형식

입력의 첫째 줄에 네 정수 $$L$$ , $$N$$ , $$r_F$$ , $$r_B$$ 가 주어진다. 다음 $$N$$ 개의 줄에는 휴게소들이 주어진다. $$1$$ 과 $$N$$ 사이의 각 $$i$$ 에 대해, $$i+1$$ 번째 줄에는 $$i$$ 번째 휴게소의 위치와 그곳 풀의 맛있음을 나타내는 두 정수 $$x_i$$ 와 $$c_i$$ 가 주어진다.

$$r_F > r_B$$ 이고 $0 < x_1 < \dots < x_N < L$ 임이 보장된다. ** $$r_F$$ 와 $$r_B$$ 는 미터당 초 단위로 주어진다는 점에 유의하라! **

출력 형식

베시가 얻을 수 있는 최대 총 맛있음 단위를 나타내는 정수 하나를 출력한다.

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:

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

예제 1

입력

10 2 4 3
7 2
8 1

출력

설명

In this example, it is optimal for Bessie to stop for $$7$$ seconds at the $$x=7$$ rest stop (acquiring $$14$$ tastiness units) and then stop for an additional $$1$$ second at the $$x=8$$ rest stop (acquiring $$1$$ more tastiness unit, for a total of $$15$$ tastiness units).

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Silver

올림피아드 > USACO > 2017-2018 > February > Silver

태그

JudgeUSACO

휴게소

평가 및 의견

풀이 제출