Cod sursa(job #1738647)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 7 august 2016 13:14:46
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int n;
vector<int> bete;

int binSearch (int sum, int poz)
{
	int st = poz;
	int dr = n-1;
	int last = -1;
	int m;
	while (st <= dr)
	{
		m = st + (dr - st)/2;
		if (bete[m] <= sum)
		{
			last = m;
			st = m+1;
		}
		else
		{
			dr = m-1;
		}
	}
	if (last != -1)
	{
		return last - poz + 1;
	}
	else
		return 0;
}

int main ()
{
	int nrc = 0;
	fin>>n;
	//bete.resize(n);
	for (int i = 1; i<=n;i++)
	{
		int x;
		fin>>x;
		bete.push_back(x);
	}
	//cout<<n<<endl;
	sort (bete.begin(), bete.end());
	//for (unsigned int i = 0; i < bete.size(); i++)
	//{
	//	cout<<bete[i] << endl;
	//}
	for (int i = 0; i <= n-3; i++)
	{
		for (int j = i+1; j <= n-2; j++)
		{
			int temp = binSearch (bete[i] + bete[j], j+1);
			nrc += temp;
		}
	}
	fout<<nrc<<"\n";
}