USACO 2018 January Contest Silver Division - Rental Service

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We sort all data and use suffix sums. We want to sell the ones with the least production and sell the milk of the ones with the most production. We can keep track of it and iterate a divider between those two categories.

Source code

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

#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef long long ll;

int n, m, r;
ll milk[100002];
pair<ll, ll> shop[100002];
ll rent[100002], ss[100002];

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

    cin >> n >> m >> r;
    for(int i = 1; i <= n; ++i)
        cin >> milk[i];
    for(int i = 1; i <= m; ++i)
        cin >> shop[i].se >> shop[i].fi;
    for(int i = 1; i <= r; ++i)
        cin >> rent[i];
    sort(milk + 1, milk + n + 1);
    sort(shop + 1, shop + m + 1);
    sort(rent + 1, rent + r + 1);
    for(int i = r; i >= 1; --i)
        ss[i] = ss[i+1] + rent[i];
    ll sum_milk = 0;
    ll rem_milk = 0;
    int poz = m;
    ll ans = 0;
    for(int i = 0; i <= n; ++i)
    {
        ans = max(ans, sum_milk + ss[max(0, r-(n-i)+1)]);
        rem_milk += milk[n-i];
        while(poz && rem_milk)
        {
            if(rem_milk >= shop[poz].se)
                rem_milk -= shop[poz].se, sum_milk += 1LL * shop[poz].se * shop[poz].fi, --poz;
            else
                shop[poz].se -= rem_milk, sum_milk += 1LL * rem_milk * shop[poz].fi, rem_milk = 0;
        }
        cout << sum_milk << '\n';
    }
    cout << ans << '\n';
    return 0;
}