USACO Silver 2018/Jan/2: Rental

Problems and Contests
#1

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[0].second){
      milk[0].second-=c;
      return(c*milk[0].first);
    }
    else if (c==milk[0].second){
      int ans=milk[0].second*milk[0].first;
      milk.erase(milk.begin());
      return(ans);
    }
    else{
      int x=c-milk[0].second;
      int ans=milk[0].second*milk[0].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]=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]=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[0];
  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
#2

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
#3

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

2 Likes