# USACO Silver 2018/Jan/2: Rental

Hi, I need help with this problem. The following is my code:

``````#include <iostream>
#include <bits/stdc++.h>
#include <array>
#include <fstream>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;

vector<int> cows;
vector<pair<int, int>> milk;
vector<int> rent;

int maxMilk(int c){
if (milk.size()==0){
return 0;
}
else{
if (c<milk.second){
milk.second-=c;
return(c*milk.first);
}
else if (c==milk.second){
int ans=milk.second*milk.first;
milk.erase(milk.begin());
return(ans);
}
else{
int x=c-milk.second;
int ans=milk.second*milk.first;
milk.erase(milk.begin());
ans += maxMilk(x);
return(ans);
}
}
}

int main() {
ifstream fin("rental.in");
long long int N, M, R, k, p, q;
fin>>N>>M>>R;
for (int i=0; i<N; i++){
fin>>k;
cows.push_back(k);
}
for (int i=0; i<M; i++){
fin>>q>>p;
pair<int, int> x=make_pair(p, q);
milk.push_back(x);
}
for (int i=0; i<R; i++){
fin>>k;
rent.push_back(k);
}
fin.close();
sort(cows.rbegin(), cows.rend());
sort(milk.rbegin(), milk.rend());
sort(rent.rbegin(), rent.rend());

long long int x[N+1], t=0;
x=0;
for (int i=1; i<=N; i++){
t+=maxMilk(cows[i-1]);
x[i]=t;
}

long long int y[N+1];
t=0, y=0;
for (int i=1; i<=N; i++){
t += rent[i-1];
y[i]=t;
}

ofstream fout("rental.out");
vector<long long int> v;
for (int i=0; i<=N; i++){
v.push_back(x[i]+y[N-i]);
}
sort(v.rbegin(), v.rend());
fout<<v;
fout.close();

}
``````

For this code I time out for cases 8, 9, 10, but when I looked at the official solution it seems to be the exact same thing as what I did. I’m pretty sure I time out because of my algorithm for finding x(1), x(2), …, x(N), but isn’t the time complexity of it just O(M+N), because it runs through all M pairs in milk and runs through all the cows at most one extra time?

Could someone please tell me what I’m doing wrong?

1 Like

I can’t look through rn, sorry.

But I think you can just sort and make a prefix sum, like for the sample input you’d get

7
13
17
19
20
10 250
25 475
27 495
250
350
430
470

and then you can just make a loop on the profit if you rent k cows where k is in the range 0 to n, then take the max

I solved this in python, but idk how to do the code thing XD

1 Like

`milk.erase(milk.begin());` takes time proportional to the size of the vector.

2 Likes