Cod sursa(job #1898822)

Utilizator flibiaVisanu Cristian flibia Data 2 martie 2017 12:01:12
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, a[850], k, x, rs;

int bins(){
	int st = 1, dr = n, piv;
	while(st <= dr){
		piv = (st + dr)/2;
		if(a[piv] <= x) st = piv + 1;
		else dr = piv - 1;
	} 
	return dr;
}

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