Cod sursa(job #1594004)

Utilizator valentin50517Vozian Valentin valentin50517 Data 9 februarie 2016 09:07:44
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <algorithm>

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

bool comp(int a,int b) {return a < b;}
int N,A[1000],rs;
int cbin(int lim,int val){
	int step,i;
	for(step = 1;step < lim;step<<=1);
	for(i = 1;step;step>>=1)
		if(i+step < lim && A[i+step] <= val)
			i+=step;
	return i;
}

int main(){
	fin >> N;
	for(int i = 1;i<=N;i++){
		fin >> A[i];
	} 
	
	sort(A,A+N,comp);
	for(int i = N;i>0;i--)
		for(int j = i-1;j>1;j--){
			int dr = cbin(j,A[i] + A[j]);
			int st = cbin(j,max(A[i],A[j])-min(A[i],A[j]));
			//fout << st << ' ' << dr << ' ' << dr-st+1 - bool(A[st] < max(A[i],A[j])-min(A[i],A[j])) - bool(A[dr] > A[i] + A[j]) << '\n';
			rs+= dr-st+1 - bool(A[st] < max(A[i],A[j])-min(A[i],A[j])) - bool(A[dr] > A[i] + A[j]);
		}
	fout << rs;
			
			
	return 0;
}