Cod sursa(job #373753)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 14 decembrie 2009 23:13:23
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>
#include <algorithm>
#define DIM 805
using namespace std;

int a[DIM], i , N, sol;

int caut ( int left, int right, int ind)
{   
    int cnt = right+1;
    int val = 0;
    int mid; 
    while ( left <= right )
    {
	mid = (left +right) >> 1 ;
        if ( a[cnt] + a[mid] >= a[ind] )	
	{
	   val = cnt-mid;
	   right = mid-1;
	}
	else left = mid +1;
    }
    return val;
}
void solve()
{
    scanf("%d\n",&N);
    for ( i=1; i<=N; i++) scanf ("%d",&a[i]);
    sort (a+1, a+N+1);    
    for ( i=N; i>=1; i--)
    {
       sol += caut (1, i-2, i );
    }
    printf ("%d\n",sol);
}
int main()
{
    freopen ("nrtri.in","r",stdin);
    freopen ("nrtri.out","w",stdout);
    solve();
    return 0;
}