#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define Store pair<ll, ll>
bool cmp(Store a, Store b) {
return a.second > b.second;
}
int main() {
freopen("rental.in", "r", stdin);
freopen("rental.out", "w", stdout);
ll N, M, R;
cin >> N >> M >> R;
vector<ll> cows(N);
for (ll i = 0; i < N; i++) {
cin >> cows[i];
}
sort(all(cows), greater<int>());
vector<Store> stores(M);
for (ll i = 0; i < M; i++) {
cin >> stores[i].first >> stores[i].second;
}
sort(all(stores), cmp);
vector<int> rents(R);
for (ll i = 0; i < R; i++) {
cin >> rents[i];
}
sort(all(rents), greater<int>());
ll profit = 0;
while (cows.size() > 0) {
ll frontCow = cows[0];
ll lastCow = cows[cows.size() - 1];
ll maxRent = rents[0];
ll maxStore = 0;
vector<Store> temp = stores;
for (ll i = 0; i < M; i++) {
ll maxGal = min(stores[i].first, frontCow);
maxStore += maxGal * stores[i].second;
frontCow -= maxGal;
stores[i].first -= maxGal;
if (frontCow == 0) {
break;
}
}
if (maxStore >= maxRent) {
profit += maxStore;
cows.erase(cows.begin());
} else {
stores = temp;
profit += maxRent;
rents.erase(rents.begin());
cows.erase(cows.end());
}
}
cout << profit << endl;
}
My code keeps returning:
Time limit exceeded on sample input case – details below
Your output file rental.out: The correct answer: 725
on the usaco submission portal.
It works perfecttly fine locally, but not on the usaco website.
I’ve tried commenting out lines and even changed everything to long long, but my code still doesn’t work there.