Cod sursa(job #941047)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 17 aprilie 2013 20:26:13
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb

#include <cstdio>
#include <algorithm>

const int MAX_N(801);

long long result;
int n;
int v [MAX_N];

inline void read (void)
{
	std::freopen("nrtri.in","r",stdin);
	std::scanf("%d",&n);
	for (int i(1) ; i <= n ; ++i)
		std::scanf("%d",&v[i]);
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("nrtri.out","w",stdout);
	std::printf("%lld\n",result);
	std::fclose(stdout);
}

inline void compute (void)
{
	std::sort(v + 1,v + n + 1);
	int i, j;
	for (i = 1 ; i < n ; ++i)
		for (j = i + 1 ; j < n ; ++j)
			result += (std::upper_bound(v + j + 1,v + n + 1,v[i] + v[j]) - v - 1) - j;
}

int main (void)
{
	read();
	compute();
	print();
	return 0;
}