Cod sursa(job #230180)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 13 decembrie 2008 10:52:20
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.46 kb
#include <algorithm>
#include <stdio.h>
using namespace std;

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int i,n,a[801],j,s=0;
	int sum[30005]={0};
	scanf("%d",&n);
	for (i=1; i<=n; i++)
	{		
        scanf("%d",&a[i]);
		++sum[a[i]];
	}
	for(i=1;i<=30000;++i)
		sum[i]+=sum[i-1];
	sort (a+1, a+n+1);
	for (i=1; i<=n-2; i++)
		for (j=i+1; j<=n-1 && a[i]+a[j]<=30000 ; j++)
			s+=sum[a[i]+a[j]]-j;
    printf("%d",s);	
	return 0;
}