Cod sursa(job #3141259)

Utilizator sireanu_vladSireanu Vlad sireanu_vlad Data 13 iulie 2023 13:46:14
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <iostream>
#include <algorithm>
using namespace std;

int n, a[801], ans;

int upper_bound(int x)
{
	int index = 0;
	for(int bit = 9; bit >= 0; bit--)
	{
		index += (1<<bit);
		if(index > n || a[index] > x)
			index -= (1<<bit);
	}
	return index;
}

int main()
{
	freopen("nrtri.in" , "r" , stdin);
    freopen("nrtri.out" , "w" , stdout);
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	sort(a+1, a+n+1);

	for(int i = 1; i <= n; ++i)
		for(int j = i+1; j <= n; ++j)
			ans += upper_bound(a[i] + a[j]) - j;

	cout << ans;
	return 0;
}