USACO 2018 February Contest, Silver
Problem 1. Rest Stops
Contest has ended.
Log in to allow submissions in analysis mode
Bessie, however, is allowed to take rest stops, where she might find some tasty grass. Of course, she cannot stop just anywhere! There are $N$ rest stops along the trail ($1 \leq N \leq 10^5$); the $i$-th stop is $x_i$ meters from the start of the trail ($0 < x_i < L$) and has a tastiness value $c_i$ ($1 \leq c_i \leq 10^6$). If Bessie rests at stop $i$ for $t$ seconds, she receives $c_i \cdot t$ tastiness units.
When not at a rest stop, Bessie will be hiking at a fixed travel rate of $r_B$ seconds per meter ($1 \leq r_B \leq 10^6$). Since Bessie is young and fit, $r_B$ is strictly less than $r_F$.
Bessie would like to maximize her consumption of tasty grass. But she is worried about Farmer John; she thinks that if at any point along the hike she is behind Farmer John on the trail, he might lose all motivation to continue!
Help Bessie find the maximum total tastiness units she can obtain while making sure that Farmer John completes the hike.
INPUT FORMAT (file reststops.in):
The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest stop and the tastiness of the grass there.It is guaranteed that $r_F > r_B$, and $0 < x_1 < \dots < x_N < L $. Note that $r_F$ and $r_B$ are given in seconds per meter!
OUTPUT FORMAT (file reststops.out):
A single integer: the maximum total tastiness units Bessie can obtain.SAMPLE INPUT:
10 2 4 3 7 2 8 1
SAMPLE OUTPUT:
15
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).
Problem credits: Dhruv Rohatgi