Cod sursa(job #2857522)

Utilizator Darius_CDarius Chitu Darius_C Data 25 februarie 2022 18:42:59
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
// Numarare triunghiuri.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#define DIM 806
std::ifstream fin("nrtri.in");
std::ofstream fout("nrtri.out");
using namespace std;
typedef long long ll;

int N, A[DIM];
ll ans = 0;

void Read()
{
	fin >> N;
	for (int i = 1; i <= N; i++)
		fin >> A[i];
}

int BinarySearch(int st, int dr, int x)
{
	int poz = -1;
	while (st <= dr)
	{
		int mij = (st + dr) / 2;
		if (A[mij] <= x)
		{
			poz = mij;
			st = mij + 1;
		}
		else
			dr = mij - 1;
	}
	return poz;
}

void Solve()
{
	for (int i = 1; i <= N; i++)
		for (int j = i + 1; j <= N; j++)
		{
			int poz = BinarySearch(j + 1, N, A[i] + A[j]);
			if (poz != -1)
				ans = 1LL * (ans + poz - j);
		}
	fout << ans;
}

int main()
{
	Read();
	sort(A + 1, A + N + 1);
	Solve();
	return 0;
}