Cod sursa(job #1205952)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 8 iulie 2014 15:27:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int N,V[805],s;
int bsearch(int st,int dr,int val)
{
    int mid;
	while(st<=dr){
		mid=(st+dr)/2;
		if(V[mid]<=val)
		         st=mid+1;
		else dr=mid-1;
   }
   mid=(st+dr)/2;
   while(V[mid]>val)
                  mid--;
    return mid;
}
int main () {
	int i,j,k;
	cin>>N;
	for(i=1;i<=N;i++)
	            cin>>V[i];
	sort(V+1,V+N+1);
	for(i=1;i<=N-2;i++)
	    for(j=i+1;j<=N-1;j++){
	            k=bsearch(j+1,N,V[i]+V[j]);
	            if(k>j-1)
				   s=s+(k-j);
				   }
	cout<<s;
   return 0;
}