Cod sursa(job #1595098)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 9 februarie 2016 22:27:49
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int N, A[810], rs, poz;
int main(){
	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> A[i];
	sort(A+1, A+N+1);
	for(int i = 1; i <= N-2; i++){
		for(int j = i+1; j <= N-1; j++){
			int sum = A[i] + A[j];
			poz = upper_bound(A+1 , A+N+1, sum) - A;
			if(A[poz] > sum) {
			poz--;
			rs+= poz - j;
			}else	
			rs += poz - j - 1;
		}
	}	
	cout <<rs;
	return 0;
}