Cod sursa(job #913841)

Utilizator ELHoriaHoria Cretescu ELHoria Data 13 martie 2013 20:03:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#include <algorithm>

using namespace std; 

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

const int nmax = 802;
int n;
int L[nmax];

int main()
{
	cin>>n;
	for(int i = 1;i <= n;i++) {
		cin>>L[i];
	}
	int Log2;
	for(Log2 = 1;Log2 <= n;Log2 <<= 1);

	sort(L + 1,L + n + 1);
	int ans = 0;
	for(int i = 1;i <= n;i++) {
		for(int j = i + 1;j < n;j++) {
			int ab = L[i] + L[j];
			int pos = j + 1;
			if(L[pos] > ab) continue;
			for(int step = Log2;step > 0;step >>= 1) {
				if(pos + step <= n && L[pos + step] <= ab) {
					pos += step;
				}
			}
			ans += pos - j;
		}
	}
	cout<<ans;
	return 0;
}