Cod sursa(job #2663334)

Utilizator NeoxDragos Stefan Neox Data 26 octombrie 2020 07:30:16
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
const int nmax = 800;
int n, i, j, c, s, v[nmax];
int cb(int st, int dr, int x) {
	int m, p;
	while(st <= dr) {
		m = (st+dr)/2;
		if(x >= v[m])
			st = m+1, p = m;
		else
			dr = m-1;
	}
	return p;
}
int main()
{
	fin >> n;
	for(i = 0; i < n; i++)
		fin >> v[i];
	sort(v, v+n);
	for(i = 0; i < n-2; i++)
		for(j = i+1; j < n-1; j++) {
			s = v[i]+v[j];
			if(s >= v[j+1])
				c += cb(j+1, n-1, s)-j;
		}
	fout << c;
	fin.close();
	fout.close();
	return 0;
}