Cod sursa(job #241076)

Utilizator ilincaSorescu Ilinca ilinca Data 9 ianuarie 2009 12:27:33
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#include <algorithm>

#define nmax 805
#define vmax 30005

using namespace std;

int n, v [nmax], f [5*vmax];



void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i<=n; ++i)
		scanf ("%d", &v [i]);
}

void init ()
{
	int i;
	for (i=1; i<=n; ++i)
		f [v [i]]=i;
	for (i=0; i<=v [n]; ++i)
	{	
		if (!f [i])
			f [i]=f [i-1];
	}
}

int nrtri ()
{
	int i, j, num=0;
	for (i=1; i<=n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			if (v [i]+v [j] > v [n])
				f [v [i]+v [j]]=f [v [n]];
			num+=f [v [i]+v [j]]-j;
		}
	return num;
}

int main ()
{
	freopen ("nrtri.in", "r", stdin);
	freopen ("nrtri.out", "w", stdout);
	scan ();
	sort (v+1, v+1+n);
	init ();
	printf ("%d\n", nrtri ());
	return 0;
}