Cod sursa(job #1255044)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 4 noiembrie 2014 09:57:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[802];

int search(int l, int r, int k)
{
	int mid;
	while(l <= r){
		mid = (l + r) / 2;
		if(a[mid] <= k)
			l = mid + 1;
		else
			r = mid - 1;
	}
	while(a[mid] > k)
		mid --;
  return 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",&a[i]);
	sort(a,a + n);
	int m = 0;
	for(int i = 0; i < n - 2; i++)
		for(int j = i + 1; j < n - 1; j++){
			 m += (search( j + 1, n - 1, a[i] + a[j]) - j);
		}	
	printf("%d\n",m);
	return 0;
}