Cod sursa(job #2430129)

Utilizator StefanSanStanescu Stefan StefanSan Data 12 iunie 2019 20:50:46
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAX 1000001

using namespace std;

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

int a[MAX], n, nr = 0;



int main() {
	in >> n;
	for (int i = 1; i <= n; i++) {
		in >> a[i];
	}
	sort(a, a + n + 1);
	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {


			int left = j + 1, right = n, sol = -1;
			while (left <= right)
			{
				int mid = (left + right) / 2;
				if (a[mid] <= a[i] + a[j])
					left = mid + 1, sol = mid;
				else
					right = mid - 1;
				
			}
			if (sol != -1) nr += (sol - j);


		}
	}
	out << nr;
}