Cod sursa(job #502119)

Utilizator skullLepadat Mihai-Alexandru skull Data 17 noiembrie 2010 20:00:36
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define pt(i) (1<<(i))
#define nmax 805

int n, rez;
int vec[nmax];

void citire ()
{
	int i;
	freopen("nrtri.in","r",stdin);
	scanf("%d", &n);
	for (i = 1; i <= n; ++i)
		scanf("%d", &vec[i]);
}

void solve ()
{
	int i, j, k, ii;
	for (i = 1; i <= n - 2; ++i)
		for (j = i+1; j <= n-1; ++j)
		{
			k = j;
			for (ii = 10; ii>=0; --ii)
				if (pt(ii)+k<=n && vec[j]+vec[i]>=vec[k+pt(ii)])
					k += pt(ii);
			rez += k-j;
		}
	freopen("nrtri.out","w",stdout);
	printf("%d", rez);
}

int main ()
{
	citire ();
	sort(vec+1, vec+n+1);
	solve ();
	return 0;
}