I am using lower_bound and still getting TLE , i even optimised it further (reduced search space, optimization using 2*b<c expression) and still getting tle… Anyone please help… Thankx in advance…
Here is my code--------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
while(true)
{
ll n;
cin>>n;
vector v;
for(ll i=0;i<n;i++)
{
ll item;
cin>>item;
v.push_back(item);
}
sort(v.begin(),v.end());
ll final=0;
for(ll i=n-1;i>1;i--)
{
ll c=v[i];
for(ll j= i-1;j>0;j--)
{
ll b= v[j];
if(2*b<c)
{
final+=((j)*(j+1))/2;
break;
}
else
{
vector<ll>::iterator ptr = v.begin();
// Using advance() to increment iterator position
// points to 4
advance(ptr, j);
ll a = lower_bound(v.begin(),ptr,c-b)-v.begin();
if(a>=j)
{
final+=j;
}
else
{
final+=a;
}
}
}
}
cout<<final<<"\n";
ll x;
cin>>x;
if(x==0)
{
break;
}
}
}