Pagini recente » Cod sursa (job #92922) | Cod sursa (job #527150) | Cod sursa (job #1455396)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n;
long int sol = 0;
vector <int> a;
void quicksort(int x,int y)
{
if(x<y)
{
int i=x,j=y,pivot = a[x];
while(i<j)
{
if(a[i]>a[j])
{
int h= a[i];
a[i] = a[j];
a[j] = h;
}
if(a[i] == pivot)
j--;
else
i++;
}
int m =i;
quicksort(x,m-1);
quicksort(m+1,y);
}
}
int bin_search(int x,int y,int val)
{
if(x<=y)
{
int m = (x+y)/2;
if(((a[m]<=val)&&(a[m+1]>val))||(m==a.size()-1))
return m;
else
{
if(a[m]>val)
return bin_search(x,m-1,val);
else
return bin_search(m+1,y,val);
}
}
}
int main()
{
in>>n;
int x;
in.close();
for(int i=1;i<=n;i++)
{
in>>x;
a.push_back(x);
}
quicksort(0,a.size()-1);
for(int i =0;i<a.size()-1;i++)
{
int x = bin_search(i+1,a.size()-1,a[i]+a[i+1]);
int y = x-i-1;
if(y>0)
sol+=y;
}
out<<sol;
out.close();
return 0;
}