Cod sursa(job #2211791)

Utilizator primeBasso Nicolae prime Data 11 iunie 2018 21:15:31
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int i, j, n, sum, x, a[801], mx = 1024, c;

int bs(){
	int step = mx, s = 0;
	
	while(step > 0){
		if(s + step <= n && a[s + step] <= sum)
			s += step;
	
		step /= 2;
	}	
	
	return s;
}

int main(){
	in >> n;
	
	for(i = 1; i <= n; i++)
		in >> a[i];
		
	sort(a + 1, a + n + 1);
	
	for(i = 1; i <= n - 1; i++)
		for(j = i + 1; j <= n; j++){
			sum = a[i] + a[j];
			x = bs();
			c += x - j;
		}
	
	out << c;
	
	return 0;	
}