Cod sursa(job #307784)

Utilizator cotofanaCotofana Cristian cotofana Data 24 aprilie 2009 22:55:47
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <cstdio>
#include <algorithm>
#define dim1 810
#define dim2 30010

using namespace std;

int n, v[dim1], inq[dim2];

int main()
{
	int i, j, k;
	long long ct=0;
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);
	scanf("%d\n", &n);
	for (i=1; i<=n; i++) scanf("%d ", &v[i]);
	sort(v+1, v+n+1);
	for (i=1; i<=n; i++) inq[v[i]]=i;
	for (i=1; i<n-1; i++)
		for (j=i+1; j<n; j++)
		{
			k=v[i]+v[j];
			while (!inq[k]) k--;
			ct+=inq[k]-j;
		}
	printf("%lld\n", ct);
	return 0;
}