Cod sursa(job #350079)

Utilizator bogdanacmDrutu Bogdan bogdanacm Data 22 septembrie 2009 17:11:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 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[i]+A[j] >= A[h])
				h++;
			sum+= h - j - 1;
			//printf("H:%d %d Sum:%ld\n",A[i]+A[j],h,sum);

		}

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