Cod sursa(job #137994)

Utilizator ScrazyRobert Szasz Scrazy Data 17 februarie 2008 19:01:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <algorithm>

#define NM 802

using namespace std;

int a[NM];
long long sol;
int okpos;
int n;

int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);

    int i, j, k;
    scanf("%d", &n);

    for (i=1; i<=n; ++i)
	scanf("%d", &a[i]);

    sort(a+1, a+n+1);
    
    for (i=1; i<n-1; ++i)
	for (j=i+1; j<n; ++j) 
	{ 
	    int low=j+1, high=n;
	    okpos=0;
	    while(low<=high)
	    {
		int mid=(high+low)>>1; 
		if (a[i]+a[j]==a[mid])
		{
		    if (okpos<mid) okpos=mid;
		    low=mid+1;
		}
		else
		if (a[i]+a[j]>a[mid])
		{
		    if (okpos<mid) okpos=mid;
		    low=mid+1;
		}
		else high=mid-1; 
	    }

	    if (okpos>j) sol+=okpos-j;
	}

    printf("%lld", sol);

    fclose(stdin);
    fclose(stdout);

    return 0;
}