Cod sursa(job #1005324)

Utilizator lucky1992Ion Ion lucky1992 Data 4 octombrie 2013 19:55:24
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <iostream>
#include <cstdio>
#include <cstdlib> 
#include <algorithm>
#define NMAX 1000

using namespace std;

int N, l[NMAX], lo, hi, count1, mid;

int main(){

	freopen("nrtri.in", "r", stdin );
	freopen("nrtri.out", "w", stdout );
	
	scanf("%d", &N );
	for( int i = 0; i < N; i++ )
		scanf("%d", &l[i] );
	
	sort( l, l+N );
	
	for( int i = 0; i < N; i++ )
		for( int j = i+1; j < N; j++ ){
			lo = j+1;
			hi = N-1;
			int x = l[i] + l[j];
			while( lo <= hi ){
				mid = lo + (hi-lo)/2;
				if( l[mid] <= x )
					lo = mid+1;
				else
					hi = mid-1;
			}
			count1 += lo - (j+1);
		}
	
	printf("%d", count1 );
	
	return 0;

}