Cod sursa(job #588190)

Utilizator ionut_ungureanuUngureanu Vladut Ionut ionut_ungureanu Data 7 mai 2011 10:50:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define Fin "nrtri.in"
#define Fout "nrtri.out"
using namespace std;
int n,i,j,u,x,nr,st,dr,mij;
vector <int> v;

int main()
{
	freopen(Fin,"r",stdin);
	freopen(Fout,"w",stdout);
	scanf("%d",&n);
	v.push_back(0);
	for(i=1;i<=n;i++)
		{
			scanf("%d",&x);
			v.push_back(x);
		}
sort(v.begin()+1,v.end());
for(i=1;i<n;i++)
	for(j=i+1;j<=n;j++)
	{
		u=v[i]+v[j];
		if(u>=v[n])
			nr+=(n-j);
	else
		{
			st=j+1;
			dr=n;
			while(st<dr)
				{
					mij=(st+dr)/2;
					if(v[mij]<=u)st=mij+1;
					else dr=mij;
				}
			nr+=(dr-j-1);
		}
	}
	printf("%d",nr);
}