Suppose that early in the hike there is a rest stop with tastiness $c$, but later there is a rest stop with tastiness $C$, where $C > c$. Then it is never optimal for Bessie to spend any time at the first rest stop: if she did, she could spend the same amount of time at the later rest stop instead, and she would still never be behind Farmer John. So the only rest stops which Bessie might stop at are the rest stops which have more tastiness than any subsequent rest stops.

We can find these "right-maximal" rest stops in a single right-to-left scan, keeping track of the largest tastiness seen so far. Now we can simply perform a greedy algorithm: never stop at non-right-maximal rest stops. At a right-maximal rest stop, Bessie should stop there as long as possible (i.e. until Farmer John catches up with her). Then she proceeds, until the next right-maximal rest stop.

To see correctness of this greedy algorithm, suppose Bessie did not spend as long as possible at some right-maximal rest stop $r$. Then she would leave this rest stop $t$ seconds early, for some positive $t$. Suppose the next place Bessie stops is rest stop $r'$. We could improve Bessie's tastiness intake by having her spend $1$ less second at $r'$, and $1$ more second at rest stop $r$. It can be verified that Bessie will still never be behind Farmer John, and since the tastiness at $r$ is greater than the tastiness at $r'$, we improved Bessie's outcome. Therefore no optimal solution will leave a right-maximal rest stop early, and our greedy algorithm is correct.

The above algorithm can be implemented with only two scans of the input, first right-to-left and then left-to-right. So the overall time complexity is $O(N)$.

#include <iostream> #include <algorithm> using namespace std; int L,N,rf,rb; int x[100000]; int c[100000]; bool isMax[100000]; int main() { cin >> L >> N >> rf >> rb; for(int i=0;i<N;i++) cin >> x[i] >> c[i]; int mx = 0; for(int i=N-1;i>=0;i--) if(c[i] > mx) { isMax[i] = 1; mx = c[i]; } long long ans = 0; long long tf = 0; long long tb = 0; int lastx = 0; for(int i=0;i<N;i++) if(isMax[i]) { tf += (x[i] - lastx)*((long long)rf); tb += (x[i] - lastx)*((long long)rb); ans += (tf - tb)*((long long)c[i]); tb = tf; lastx = x[i]; } cout << ans << '\n'; }