# Why is my code timing out?

So I was working on this problem:
http://www.usaco.org/index.php?page=viewproblem2&cpid=714
This is my code

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_set>

using namespace std;
void fileIO(string filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
const int INTMAX=2147483647;
int main() {
fileIO("helpcross");
int C,N;
cin>>C>>N;
vector<int> chickens(C);
multiset<pair<int,int>> cows;
for(int i=0;i<C;i++){
cin>>chickens[i];
}
map<pair<int,int>,int> cowsLeft;
for(int i=0;i<N;i++){
int a,b;
cin>>a>>b;
cowsLeft[{a,b}]++;
cows.insert({a,b});
}
sort(chickens.begin(),chickens.end());
int ans=0;
for(int c=0;c<C;c++){
pair<int,int> bestCow={INTMAX,INTMAX};
for(pair<int,int> i : cows){
if(chickens[c]>=i.first && chickens[c]<=i.second && cowsLeft[i]>0){
if((i.second-chickens[c])<(bestCow.second-chickens[c])){
bestCow=i;
}
}
}
if(bestCow != make_pair(INTMAX,INTMAX)){
ans++;
cowsLeft[bestCow]--;
//  cows.erase(bestCow);
}
}
cout<<ans<<endl;
return 0;
}


This is the output:

For some reason, it is timing out despite the time complexity being O(c * n). The USACO guide also has a solution of time complexity o(c*n), which quickly passes all test cases

Why is my code timing out when it has the same time complexity?

Your code has a large constant factor. As of right now your second for loop is iterating through the cows by value, which makes a copy of each cow before processing it. I’d suggest iterating through by reference instead.

Actually, the complexity in USACO Guide is wrong … it should be O(N\log N+C\log C) (fixed now).

(Though it’s worth noting that a properly optimized O(N\cdot C) solution will pass comfortably under the TL. In fact, the model solution still works if chickens is a vector instead of a multiset …)