Cod sursa(job #2911022)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 26 iunie 2022 14:35:02
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <unordered_map>

#define NMAX 803

using namespace std;



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

int v[NMAX], n, k;



int main() {

	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		fin >> v[i];
	}
	
	stable_sort(v + 1, v + n + 1);
	//imi fixez 2 numere si o caut pe a treia
	int sol = 0;
	for (int i = 1; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			//caut binar cea de a treia valoare
			int st = j + 1, dr = n;
			while (st <= dr)
			{
				int mij = (st + dr) / 2;
				if (v[i] + v[j] >= v[mij])
				{
					//merg la dreapta
					st = mij + 1;
				}
				else {
					dr = mij - 1;
					
				}
			}
			sol += (dr - j);
		}
	}
	fout << sol;
	return 0;
}