Cod sursa(job #2454581)

Utilizator davidcotigacotiga david davidcotiga Data 9 septembrie 2019 13:23:41
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb

#include <fstream>

#include <algorithm>



using namespace std;

ifstream fin("nrtri.in");

ofstream fout("nrtri.out");

int v[800];

int cautare(int x, int st, int dr) {

	int mid;

	while (st < dr) {

		mid = st + (dr - st) / 2;

		if (v[mid] <= x)

			st = mid + 1;

		else

			dr = mid;

	}

	return st - 1;

}

int main() {

	int n, i, j, poz, cnt;

	fin >> n;

	for (i = 0; i < n; i++)

		fin >> v[i];

	sort(v, v + n);

	cnt = 0;

	for (i = 0; i < n - 1; i++) {

		for (j = i + 1; j < n; j++) {

			cnt += cautare(v[i] + v[j], j + 1, n) - j;

		}

	}

	fout << cnt;

	return 0;

}