Cod sursa(job #788618)

Utilizator ephgstefana gal ephg Data 15 septembrie 2012 14:39:24
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <cstdio>
#include<algorithm>
using namespace std;
int a[805],c,n;
int cb(int max,int i,int j){
	int mij,ma;
	for(;i<=j;){
		mij=(i+j)/2;
		if(ma==mij)break;
		if(a[mij]<max)i=mij+1;
		else j=mij-1;
		ma=mij;
	}
	if(a[i]>max||i>n)return i-1;
	return i;
}
int main () {
	int i,j,el;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(i=1;i<n-1;++i){
		for(j=i+1;j<n;++j){
			el=cb(a[i]+a[j],j,n);
			//fprintf(stderr,"%d %d %d\n",i,j,el);
			if(el>j)c+=(el-j);
		}
	}
	printf("%d",c);
	return 0;
}