Cod sursa(job #494963)

Utilizator soriynSorin Rita soriyn Data 23 octombrie 2010 14:54:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<iostream>
#include<algorithm>

using namespace std;
int V[805],N,nr;

inline int BS(int v)
{
    int st=0,dr=N-1,m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if((V[m]<=v&&V[m+1]>v)||(V[m]<=v&&m==N-1))
            return m;
        else if(V[m]<=v)
            st = m+1;
        else
            dr = m-1;
    }
    return 0;
}


int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int i,j;
	scanf("%d\n",&N);
	
	for(i=0;i<N;i++)
		scanf("%d ",&V[i]);
	sort(V,V+N);
	for(i=0;i<N;i++)
		for(j=i+1;j<N;j++)
	nr+=(BS(V[i]+V[j])-j);
	
	printf("%d",nr);
	return 0;
}