Cod sursa(job #795032)

Utilizator petiVass Peter peti Data 7 octombrie 2012 15:15:10
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream ifs("nrtri.in");
ofstream ofs("nrtri.out");
int search(int x);
vector <int> v;
int N;
int result=0;

int main(){
	
	ifs>>N;
	v.resize(N);
	for(int i=0;i<N;i++)
		ifs>>v[i];
	
	sort(v.begin(),v.end());
	for(int i=N-1;i>=2;i--){
		for(int n=i-1;n>0;n--){
			int s=search(v[i]-v[n]);
			if(s>=n) break;
			else result+=n-s;
		}
	}
	
	ofs<<result;
	return 0;
}

inline int search(int x){
	int i=0;
	while(v[i]<x)
		i++;
	return i;	
}