Cod sursa(job #350077)

Utilizator bogdanacmDrutu Bogdan bogdanacm Data 22 septembrie 2009 17:00:41
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
 
#define pb push_back
#define mp make_pair
#define NMAX 5005
#define INF 1000000

vector <int> A;
vector <int> S;



bool MySortPredicate(const int d1, const int d2)
{
	return d1 < d2;
}

int bin(int l, int h, int k)
{
	int mid = (l+h)/2;

	if (l==h)
		return l;

	if (A[mid] <= k)
		return bin(mid+1, h, k);
	else
		return bin(l,mid, k);
}

int main()
{
	int i,a,N,j,h,l;
	char buf[100];
	long sum=0;

	freopen("nrtri.in", "rt", stdin);
	freopen("nrtri.out", "wt", stdout);

	scanf("%d",&N);

	for (i=0;i<N;i++)
	{
		scanf("%d",&a);
		A.pb(a);
	}
	
	sort(A.begin(),A.end(),MySortPredicate);
	A.pb(INF);

/*	for (i=0;i<N;i++)
		printf("%d ",A[i]);
	printf("\n");
*/
	for (i=0;i<N;i++)
		for (j=i+1;j<N;j++)
		{
			h = bin(0,N,A[i]+A[j]);
			while (A[h] == A[h+1])
				h++;
//			printf("H:%d %d\n",A[i]+A[j],h);			
			
			sum+= h - j - 1;
		}

	printf("%ld\n",sum);
	return 0;
}