Cod sursa(job #497598)

Utilizator alecsandrualex cuturela alecsandru Data 2 noiembrie 2010 22:03:20
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 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;

}