# Help on TLE

Hi,
I was working on this problom from the USACO guide:

This is my code

``````#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
long long N,X;
//get sum closest to c/2
long long index(const vector<long long>& in,long long c ,const vector<long long>& psum){
long long goal=c/2;
auto iter=upper_bound(psum.begin(),psum.end(),goal);
if(iter==psum.end()){
return *--iter;
}
long long upper=*iter;
long long lower=*--iter;
if(abs(lower-goal)>abs(upper-goal)){
return upper;
}
return lower;
}
int main() {
cin>>N>>X;
vector<long long> in(X);
map<long long,long long> elements;
for(long long i=0;i<X;i++){
long long input;
cin>>input;
in[i]=input;
elements[input]++;

}
sort(in.begin(),in.end());
//calculate prefix sums so that we can calculate the closest numbers in logN time
vector<long long> psum(X+1);
for(int i=1;i<=X;i++){
psum[i]=psum[i-1]+in[i-1];
}

//queue to store the sticks
queue<long long> pq;
pq.push(N);
long long ans=0;
while(!pq.empty()){
long long top=pq.front();
if(elements[top]>0){
//if we have that stick length is one of the desired we can pop it and mark it as used
elements[top]--;
}else{
//break the current stick
long long f=index(in,pq.front(),psum);
pq.push(pq.front()-f);
pq.push(f);
ans+=pq.front();
}
//pop the last one because we broke it
pq.pop();
}
cout<<ans;
return 0;
}
``````

The time complexity is X*logX but this is at worst case and most of the time it should be well below this.
these are the results:

I am confused on how my code is timing out and how I can fix it. Can someone please help?

Thanks.

What’s the problem you’re working on?

Sorry, I forgot to add it. It should be in the post now.

Try rewriting your algorithm using a `priority_queue`. That would make your code a bit more elegant. It will also probably improve the runtime of your code.

The reason I am using a queue and not a priority_queue is that a priority queue has o(log(n)
) insertion and deletion while a queue has o(1) insertion.
With priority_queue I had 0.10 second on test 3, but with queue I had 0.7 seconds

Overall, wouldn’t the time complexity still be the same though? Regardless, it’d be O(n\log n).

Oh yeah, you are right. But the code still gets a TLE. X is fairly small so I would assume n*logN would pass, right?

Remove this after using a `priority_queue`

This isn’t necessary.

Rethink how you’re going to implement this.