Cod sursa(job #373547)

Utilizator prisonbreakMichael Scofield prisonbreak Data 14 decembrie 2009 09:51:46
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 value)
{   
    int cnt = right+1;
    int val = 0;
    int mid;
    while ( left <= right )
    {
	mid = left + ( right - left ) >> 1;
        if ( a[cnt] + a[mid] >= value ) val = cnt-mid+1, right = left-1;
	else left = right +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, a[i] );
    }
    printf ("%d\n",sol);
}
int main()
{
    freopen ("nrtri.in","r",stdin);
    freopen ("nrtri.out","w",stdout);
    solve();
    return 0;
}