USACO 2018 December Contest Silver Division - Convention II

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Use a priority queue to keep track of the available cows and have them as like the "options" and always pick the most senior one.

Source code

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

#include <algorithm>
#include <fstream>
#include <iostream>
#include <set>

using namespace std;

int n, maxi, arrival[100001], inspection[100001];

struct cows {
    int position, arrival, inspect;
};
cows v[100001];

bool cmp(cows a, cows b) { 
    return a.arrival < b.arrival; 
}
set<int> seniority;

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> v[i].arrival >> v[i].inspect;
        v[i].position = i;
        arrival[i] = v[i].arrival;
        inspection[i] = v[i].inspect;
    }

    sort(v, v + n, cmp);

    int pos = 0;
    int currentTime = 0;
    for (int i = 0; i < n; i++) {
        if (seniority.empty() && pos < n && currentTime < v[pos].arrival) {
            currentTime = v[pos].arrival;
        }
        while (pos < n && currentTime >= v[pos].arrival) {
            seniority.insert(v[pos].position);
            pos++;
        }
        int val = *seniority.begin();
        seniority.erase(val);
        maxi = max(maxi, currentTime - arrival[val]);
        currentTime += inspection[val];
    }

    cout << maxi;
    return 0;
}