Cod sursa(job #2062164)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 10 noiembrie 2017 01:51:35
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

inline void Boost() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}
typedef long long int ll;
typedef long double ld;

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

const int NMax = 850;

int v[NMax];

int Binary(int lo, int hi, const int &value) {
	int best = lo - 1;
	int bg = lo - 1;

	while(lo <= hi) {
		int mid = (lo + hi) / 2;

		if(v[mid] >= value) {
			hi = mid - 1;
		} else {
			best = mid;
			lo = mid + 1;
		}
	}

	return best - bg;
}

int main() {
	Boost();

	int n;
	fin >> n;
	
	for(int i = 1; i <= n; ++i) fin >> v[i];
	sort(v + 1, v + n + 1);

	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = i + 1; j <= n; ++j) {
			int x = Binary(j + 1, n, v[i] + v[j]);
			ans += x;
		}
	}

	fout << ans;
	return 0;
}