USACO 2021 December Contest Silver Division - Closest Cow Wins

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

For each sequence between two Nhoj's cows, with a maximum of \(2\) cows, we can take all the patches of greenery. For those at the ends (i.e. after the last, respectively the first cow) we can take all the patches with a single cow. We thus observe that, we can calculate with two pointers, for each sequence between two Nhoj's cows, the optimal amount to place a single cow in that sequence, and if we want to place two, the total amount - the optimal amount for one cow - is added to the sum. We sort all these amounts, and finally we take the first ones in the largest ones, we sum them and display the result.

Source code

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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back

const int MAX_K = 2e5, MAX_M = 2e5;

pair<int, int> grassPatchesAndCows[MAX_K + MAX_M + 5]; /* keep them together so we can sort both */
vector<ll> tastiness;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int k, m, n, i, j, x, lastPos;
    ll tastinessValue, tastinessIncrease, tastinessMax;

    cin >> k >> m >> n;
    for (i = 0; i < k; i++) {
        cin >> grassPatchesAndCows[i].first >> grassPatchesAndCows[i].second;
    }
    for (i = k; i < k + m; i++) {
        cin >> grassPatchesAndCows[i].first;
        grassPatchesAndCows[i].second = -1; /* special marking */
    }

    sort(grassPatchesAndCows, grassPatchesAndCows + k + m);

    lastPos = -1;
    tastinessValue = 0;
    for (i = 0; i < k + m; i++) {
        if (grassPatchesAndCows[i].second == -1) { /* if it's a cow */
            if (lastPos == -1) {                   /* if it's the first one */
                tastiness.pb(tastinessValue);
            } else {
                x = lastPos;
                tastinessIncrease = tastinessMax = 0;
                for (j = lastPos + 1; j < i; j++) {
                    /* two cows cannot increase the answer more than one cow can if doubled */
                    while (x + 1 < i && (grassPatchesAndCows[i].first - grassPatchesAndCows[lastPos].first) > (grassPatchesAndCows[x + 1].first - grassPatchesAndCows[j].first) * 2) {
                        x++;
                        tastinessIncrease += grassPatchesAndCows[x].second;
                    }

                    if (tastinessIncrease > tastinessMax) {
                        tastinessMax = tastinessIncrease;
                    }
                    tastinessIncrease -= grassPatchesAndCows[j].second;
                }

                tastiness.insert(tastiness.end(), {tastinessMax, tastinessValue - tastinessMax});
            }

            lastPos = i;        /* updating position */
            tastinessValue = 0; /* resetting value */
        } else {                /* if it's a grass patch */
            tastinessValue += grassPatchesAndCows[i].second;
        }
    }
    tastiness.pb(tastinessValue);

    sort(tastiness.begin(), tastiness.end());

    tastinessValue = 0;
    for (i = (int)tastiness.size() - 1; i >= tastiness.size() - min((int)tastiness.size(), n); i--) {
        tastinessValue += tastiness[i];
    }

    cout << tastinessValue;
    return 0;
}