# USACO Silver Rental Service

http://www.usaco.org/index.php?page=viewproblem2&cpid=787

I am currently going through USACO Guide, and am stuck on this problem. I know my solution is way too long for this problem, and there is a faster implementation to the problem, but I was wondering if this solution could actually work, if implemented correctly. Currently, I fail on Test Cases 5, 6, and 7. I ruled out integer overflow (I have a #define int ll), and TLE.

My thought process is to make a bunch of prefix sums, and iterate from i to n . There would be i cows that would get sold for milk, and n-i cows being sold for rent. I then find the lower bound of the total gallons of milk and find the max amount of money that could be produced by the total amount of milk. Then, for the cows being sold for rent, I simply just access the n-i element in the prefix sum for the rent values. Like I said, I can’t tell if there is a problem with my approach to this problem, or because I implemented it badly. Thanks for help in advance.

``````#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define mpa make_pair
#define pb push_back
#define ins insert
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define nl "\n"
#define gtr greater<>
#define int ll

void fileIO(string filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}

struct milk {
int amount, price;
};

bool cmp(const milk &x, const milk &y) { return x.price > y.price; }

void solve(int tc) {
int n, m, r;
cin >> n >> m >> r;
vector<int> cows(n);
vector<milk> mprices(m);
vector<int> rprices(r);
for (int i = 0; i < n; i++) {
cin >> cows[i];
}
for (int i = 0; i < m; i++) {
cin >> mprices[i].amount >> mprices[i].price;
}
for (int i = 0; i < r; i++) {
cin >> rprices[i];
}
sort(all(cows), greater<ll>());
sort(all(rprices), greater<ll>());
sort(all(mprices), cmp);
vector<int> ps(m + 1), ps1(m + 1), ps2(r + 1);
ps = 0;
for (int i = 0; i < m; i++) {
ps[i + 1] = ps[i] + mprices[i].amount;
}

ps1 = 0;
for (int i = 0; i < m; i++) {
ps1[i + 1] = ps1[i] + mprices[i].price * mprices[i].amount;
}

ps2 = 0;
for (int i = 0; i < r; i++) {
ps2[i + 1] = ps2[i] + rprices[i];
}

int ans = INT_MIN, total = 0;
for (int i = 0; i <= n; i++) {
// sweeping line
// i cows being sold for milk
// n-i cows being sold for rent
int sum = 0;
int lb = lower_bound(all(ps), total) - ps.begin();
if (lb != 0 && i <= m && lb <= n) {
// this deals with the floor case
sum += ps1[lb - 1];
////this deals with the left over
if (lb != 1) {
sum += mprices[lb - 1].price * (total % ps[lb - 1]);
} else {
sum += mprices[lb - 1].price * lb;
}
}
if (n - i <= r) {
sum += ps2[n - i];
}
ans = max(ans, sum);
if (i != n) {
total += cows[i];
}
}
cout << ans << nl;
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// fileIO("rental");
auto begin = chrono::high_resolution_clock::now();

int tc = 1;
// cin >> tc;

for (int i = 1; i <= tc; i++) {
solve(i);
}

auto end = chrono::high_resolution_clock::now();

cerr << nl << setprecision(4) << fixed
<< chrono::duration_cast<chrono::duration<double>>(end - begin).count();
}

``````

To be specific, you are getting “wrong answer” on all of these test cases?

Also, you should post the full code.

1 Like

Yes, all of them are WA. I just updated the code to be my full solution.

This seems to work:

``````    if (lb != 0) { //  && i <= m && lb <= n
// this deals with the floor case
sum += ps1[lb - 1];
////this deals with the left over
// if (lb != 1) {
if (lb <= m) sum += mprices[lb - 1].price * (total -ps[lb - 1]);
// } else {
//   sum += mprices[lb - 1].price * lb;
// }
}
``````

Though in the future, you should try stress testing first if you’re getting WA. 1 Like

Thank you! I’ll try to do stress testing from now on It seems the link’s broken. Was the page deleted or did something else happen to it?

The module was renamed.