Cod sursa(job #1897329)

Utilizator igroitaGroita Igor igroita Data 1 martie 2017 12:33:44
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>

using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

int n, a[804];

int partition(int a[100], int b, int e){
	
	int x = a[e];
	int i = b-1;
	for(int j=b; j<e; ++j){
		if(a[j]<=x){
			i++; int w;
			w = a[i]; a[i] = a[j]; a[j] = w;
		}		
	}
	int sc; sc = a[i+1]; a[i+1]=a[e]; a[e] = sc;
	return i+1;
}
void quicksort(int v[804], int b, int e){	 if(b<e){
 				   int p = partition(v, b, e);
 				   quicksort(v,b, p-1); quicksort(v,p+1,e);
	}}

int	bsearch(int v[804], int b0, int e0){
	int b = b0, e = e0;
	while(b<e){
		int mid; mid = (b+e)/2;
		if(v[b0]+v[mid]>=v[e0])  e = mid;
		else b = mid+1;
	}
	 if(b==e0) return 0;
	 if(b==b0) return e0 - b - 1;
	 return e0-b;
}
long long nrtriunghiuri(int v[804],int m){
	 long long total = 0;
	int x=1, z=3;
	for(z=3; z<=m; ++z){
		for(x=1; x<=z-2; ++x){
	 			 total=total+bsearch(v,x,z); 
	 			 
		}
	}
	return total;
}
int main(){
	cin>>n;
	
	for(int i=1; i<=n; ++i) cin>>a[i];
	
	
	quicksort(a, 1, n);	
	cout<<nrtriunghiuri(a,n);




	return 0;
}