Cod sursa(job #1659713)

Utilizator ArkinyStoica Alex Arkiny Data 22 martie 2016 15:18:41
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<fstream>
#include<algorithm>
using namespace std;

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

int N, v[1000];

int main()
{

	in >> N;

	for (int i = 1; i <= N; ++i)
		in >> v[i];

	int i, j, l, r,piv,mid;

	long long nr = 0;

	sort(v + 1, v + N + 1);

	for (i = 1; i <= N - 2; ++i)
	{
		
		for (j = i + 1; j <= N - 1; ++j)
		{
			l = j+1, r = N;

			while (l <= r)
			{
				mid = (l + r) >> 1;

				if (v[i] + v[j] < v[mid])
					r = mid - 1;
				else
					l = mid + 1;

			}

			nr += r - j,piv=r;
		}
	}

	out << nr;

	return 0;
}