Cod sursa(job #911109)

Utilizator GManiakGhenea Catalin GManiak Data 11 martie 2013 12:44:33
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[801],n,nr;
void schimb(int i,int j)
{
    int aux;
    aux=v[i];
    v[i]=v[j];
    v[j]=aux;
}
void sort(int l,int h)
{
    int piv,i=l,j=h;
    piv=(l+h)/2;
    piv=v[piv];
    while(i<=j)
    {
        while(v[i]<piv)
            i++;
        while(v[j]>piv)
            j--;
        if(i<=j)
            schimb(i++,j--);
    }
	if(i<h)
		sort(i,h);
	if(j>l)
		sort(l,j);
}
int caut(int x)
{
    int i=0,pas=1<<9;
    while(pas!=0)
    {
        if(i+pas<=n && v[i+pas]<x)
            i+=pas;
        pas/=2;
    }
    return i;
}
void solve()
{
	int x,y,z,d;
	for(x=n;x>2;x-=d)
	{
		y=caut(v[x]);
		d=x-y;
		for(;y>1;y--)
		{
			z=v[x]-v[y];
			if(z<=v[y])
				nr+=d*(y-caut(z)-1);
			else 
				break;
			
		}
	}
}
int main()
{
	in>>n;
	for(int i=1;i<=n;i++)
		in>>v[i];
	sort(1,n);
	solve();
	out<<nr;
	return 0;
}