Doubt for bench press quesion

1

this is the ques

I am getting TLE

#include
#include<bits/stdc++.h>
using namespace std;

int main()
{
int t,n,w,wr,i,p,ans,tot,j,c;

cin>>t;
while(t–)
{
w=0;tot=0;
cin>>n >> w >> wr;
int arr[n];
for(i=0;i<n;i++)
{
cin>>arr[i];
}
//logic…
if(wr>=w)
cout<<“YES”<<endl;
else

{
    sort(arr,arr+n);
    
    i=0;
while(i<n)
{
    j=i+1;
    while(j<n)
    {
    if(arr[i]!=arr[j])
    break;
    j++;
    c++;
    if(c>1)
    {
        tot=tot+c*arr[i];
        if(c%2==1)
        tot=tot-arr[i];
        if(tot>=w)
        break;
    }
    i=j;
    }
    if(tot>=w)
    cout<<"YES"<<endl;
    else
     cout<<"YES"<<endl;
}
    }
}
return 0;

}

2

why you are using two loops in here, instead it can be solved easily using 1 while loop only.
You have already sorted the array, then just compare 2 elements at a time if those two elements are equal then add that weight and increase counter by 2, if elements are not equal then just increase the counter by 1 and don’t add that weight to the ans.

3

N can go upto 10^5, so O(N^2) time complexity will definitely give TLE. Think of O(NlogN) or O(N) approach.
A easy to think O(N) approach is to use unordered_map and store frequency of each element, then just add el*(freq[el]/2)*2 to answer for each element. I will go with map because of trust issues with unordered_map and time complexity will be O(NlogN), still affordable.

4

Try Reducing Loops It Will Work @anon74541909

5

You’re literally spamming everywhere and begging for likes.

2 Likes