Problem: Rental services (2018 JAN, Silver)
At first, I thought this is gonna be an easy problem, but I ran into some bugs and cannot fix it.
My code passed test cases 1,2,3,5, and 7, but not the rest.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
return a.second<b.second;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("rental.in", "r", stdin);
//freopen("rental.out", "w", stdout);
int n,m,r;
cin>>n>>m>>r;
int cows[n];
vector<pair<int,int>> stores;
int farmers[r];
int prefixsum[r+1];
for(int i = 0;i<n;i++) cin>>cows[i];
for(int i = 0;i<m;i++) {int a,b;cin>>a>>b;stores.push_back({a,b});}
for(int i = 0;i<r;i++) cin>>farmers[i];
sort(farmers,farmers+r,greater<int>());
sort(cows, cows+n,greater<int>());
sort(begin(stores),end(stores),myComparison);
for(int i = 0;i<=r;i++) prefixsum[i] = 0;
for(int i = 1;i<=r;i++) prefixsum[i] = prefixsum[i-1] + farmers[i-1];
long long maxprofit = 0;
long long curprofit = 0;
for(int i = 0;i<n;i++){
if(stores.size()==0) break;
while(cows[i]!=0){
if(stores.size()==0) break;
int last = stores.size()-1;
if(stores[last].first>=cows[i]){
stores[last].first -= cows[i];
curprofit += stores[last].second*cows[i];
cows[i] = 0;
}else{
cows[i]-= stores[last].first;
curprofit += stores[last].second * stores[last].first;
stores[last].first = 0;
}
if(stores[last].first==0) stores.pop_back();
}
int prefixind = min(r,n-i-1);
maxprofit = max(curprofit+prefixsum[prefixind],maxprofit);
}
cout<<maxprofit<<endl;
}