Cod sursa(job #335438)

Utilizator rumburakrumburak rumburak Data 29 iulie 2009 22:56:39
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> v;
int n;

void citire()
{
	int i,x;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&x);
		v.push_back(x);
	}
}

int calcul()
{
	int i,j,k,s=0;
	for(i=0;i<n-2;++i)
	{
		k=i+2;
		for(j=i+1;k<n;++j)
		{
			while(k<n && v[k]<=v[i]+v[j])
				++k;
			s+=k-j-1;
		}
	}
	return s;
}

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	citire();
	sort(v.begin(),v.end());
	printf("%d\n",calcul());
	return 0;
}