Cod sursa(job #574600)

Utilizator deneoAdrian Craciun deneo Data 7 aprilie 2011 12:30:32
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include<fstream>
#include<algorithm>
using namespace std;

int v[802], n;

int _search(int k) {
	int poz = 0;
	for(int i = 1 << 10; i; i >>= 1)
		if(i + poz <= n && v[i + poz] <= k)
			poz += i;
	return poz;
}

int main() {
	int i, j, rez = 0, u;
	ifstream f("nrtri.in");
	ofstream g("nrtri.out");
	f >> n;
	for(i = 1; i <= n; ++i)
		f >> v[i];
	sort(v + 1, v + 1 + n);
	for(i = 1; i < n -1; ++i)
		for(j = i + 1; j < n; ++j) {
			if((u = _search(v[i] + v[j]) - j) > 0)
				rez += u;
		}
	g << rez << '\n';
	g.close();
	return 0;
}