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] = 0;
for (int i = 0; i < m; i++) {
ps[i + 1] = ps[i] + mprices[i].amount;
}
ps1[0] = 0;
for (int i = 0; i < m; i++) {
ps1[i + 1] = ps1[i] + mprices[i].price * mprices[i].amount;
}
ps2[0] = 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();
}
