Cod sursa(job #779998)

Utilizator crushackPopescu Silviu crushack Data 19 august 2012 17:26:56
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <stdio.h>
#include <algorithm>
#define NMax 810
using namespace std;

const char IN[]="nrtri.in",OUT[]="nrtri.out";

int N,Rez;
int v[NMax];

int search(int x){
	int i,step;
	for (step=1;step<=N;step<<=1);
	for (i=0;step;step>>=1)
		if (i+step<=N && v[i+step]<=x)
			i+=step;
	return i;
}

int main()
{
	int i,j;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=1;i<=N;++i) scanf("%d",v+i);
	fclose(stdin);

	sort(v+1,v+N+1);

	for (i=1;i<=N;++i)
		for (j=i+1;j<=N;++j)
			Rez+=max(0,search(v[i]+v[j])-j);

	freopen(OUT,"w",stdout);
	printf("%d\n",Rez);
	fclose(stdout);

	return 0;
}