USACO 2018 February Contest Silver Division - Rest Stops

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The greatest possible rest stop (greater than all prior ones that haven't been taken) is the optimal rest stop. Iterate backwards to find the stops Bessie rests at and iterate through them to find the answer.

Source code

The source code in C++ can be seen below.

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct rest {
    int pos;
    int tasty;
};

int main() {
    ifstream cin("reststops.in");
    ofstream cout("reststops.out");

    int l, n, rf, rb;
    cin >> l >> n >> rf >> rb;

    vector<rest> stops(n);
    for (int i = 0; i < n; i++) {
        cin >> stops[i].pos >> stops[i].tasty;
    }

    vector<rest> rel;
    int best = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (stops[i].tasty > best) {
            rel.push_back(stops[i]);
            best = stops[i].tasty;
        }
    }

    reverse(rel.begin(), rel.end());

    long long units = 0;
    int pos = 0;
    for (auto stop : rel) {
        int dist = stop.pos - pos;
        long long time = 1LL * dist * (rf - rb);
        units += time * stop.tasty;
        pos = stop.pos; 
    }

    cout << units << '\n';
    return 0;
}