Cod sursa(job #754203)

Utilizator gener.omerGener Omer gener.omer Data 31 mai 2012 23:25:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

#define NMAX 805

int A[NMAX];

int main(){
	ifstream in("nrtri.in");
	ofstream out("nrtri.out");
	int N;
	in >> N;
	for(int i = 0; i < N; ++i)
		in >> A[i];
	vector<int> v (A, A + N);
	sort(v.begin(), v.end());
	int sz = N;
	
	vector<int>::iterator upper, lower;
	int nr = 0;
	
	for(int i = 0; i < sz; ++i)
		for(int j = i + 1; j < sz; ++j){
			upper = upper_bound(v.begin(), v.end(), v[i] + v[j]);
			nr += int(upper - v.begin()) - j - 1;
		}
			
	out << nr;
	
	return 0;
}