Cod sursa(job #788613)

Utilizator ephgstefana gal ephg Data 15 septembrie 2012 14:30:27
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <cstdio>
#include<algorithm>
using namespace std;
int a[805],c;
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)return i-1;
	return i;
}
int main () {
	int n,i,j,el;
	freopen("ntri.in","r",stdin);
	freopen("ntri.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;
}