USACO 2017 US Open Contest Silver Division - Paired Up

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

After sorting the pairs, we can use a two pointers like approach to match the extremes as this allows us to keep the sums as small as possible.

Source code

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

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

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

    int N; 
    cin >> N;

    vector<pair<int, int>> milk(N);
    for(int i = 0; i < N; i++) { 
        cin >> milk[i].se >> milk[i].fi; 
    }

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

    int l = 0, r = N - 1, ans = -1;
    while(l < r) {
        int cur = min(milk[l].se, milk[r].se);

        ans = max(ans, milk[l].fi + milk[r].fi);

        milk[l].se -= cur; 
        milk[r].se -= cur;

        if(milk[l].se == 0){ 
            l++; 
        }
        if(milk[r].se == 0){ 
            r--; 
        }
    }

    cout << ans << '\n';
    return 0;

}