Cod sursa(job #1521831)

Utilizator Vladut-Vlad Panait Vladut- Data 10 noiembrie 2015 21:21:41
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <algorithm>
#define MAXN 805

using namespace std;

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

int n, v[MAXN];
int sol, sol1;

void caut_bin(int left, int right, int value)
{
	while (left < right)
	{
		int m = ((left + right) >> 1) + 1;
		if (value >= v[m])
		{
			left=m;
		}
		else
		{
			right=m-1;
		}
		sol1 = left;
	}
	
}

int main()
{
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		fin >> v[i];
	}

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			caut_bin(j, n, v[i]+v[j]);
			sol += sol1-j;
		}
	}

	fout << sol;

	return 0;
}