Cod sursa(job #938061)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 11 aprilie 2013 18:05:41
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
int N,a[2000],v[60001],i,j,k,n,m;
int pivot(int i,int j)
{int i1=0,j1=1,x;
 while(i<j)
 {if(a[i]>a[j])
	 {x=a[i];a[i]=a[j];a[j]=x;
	  x=i1;i1=j1;j1=x;}
  i+=i1;j-=j1;}
 return i;}
void sort(int i,int j)
{if(i<j)
 {int k=pivot(i,j);
  sort(i,k-1);
  sort(k+1,j);}}
int main()
{freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&N);
for(i=0;i<N;++i)	scanf("%d",&a[i]);
sort(0,N-1);k=a[N-2]+a[N-1];
for(i=0;i<=k;++i) 
	{int s=0,d=N-1;v[i]=0;
	 while(s<=d)
	 {m=(s+d)/2;
	  if(i<a[m]) d=m-1;
	  else {v[i]=m;
		  s=m+1;}}}
for(i=0;i<N-2;++i)
	for(j=i+1;j<N-1;++j)
		 n+=v[a[i]+a[j]]-j;
printf("%d",n);
return 0;
}