Cod sursa(job #526162)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 27 ianuarie 2011 16:23:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	freopen ("nrtri.in", "r", stdin);
	freopen ("nrtri.out", "w", stdout);

	int N;
	vector <int> B;
	
	scanf ("%d", &N);
	
	for (int i = 0; i < N; ++i)
	{
		int numar;
		
		scanf ("%d", &numar);
		B.push_back(numar);
	}	
	
	sort (B.begin(), B.end());
	
	int rezultat = 0;
	
	for (int i = 0; i < N - 2; ++i)
	{
		int ind = i;
		
		for (int j = i + 1; j < N - 1; ++j)
		{
			int lim = B[i] + B[j];
			
			while (ind <= j) ++ind;
			while (ind < N - 1 && B[ind] <= lim) ++ind;
			
			if (B[ind] > lim) -- ind;
			
			rezultat += (ind - j);
		}	
	}
	
	printf ("%d", rezultat);
	
	return 0;
}