Cod sursa(job #2259917)

Utilizator pionierul22aNa LiZa pionierul22 Data 13 octombrie 2018 22:48:22
Problema Numarare triunghiuri Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,s,v[800];

int cauta(int i1,int j1,int s)
{
    if(i1==j1)
    {
        if(s>=v[i1])
            return i1;
        else
            return 0;
    }

    if(v[i1]>s)
        return 0;

    int mijl=(i1+j1)/2;

    int M1=cauta(i1,mijl,s);
    int M2=cauta(mijl+1,j1,s);

    return max(M1,M2);
}

int main()
{
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>v[i];

	sort(v+1,v+n+1);

	for (int i=1;i<=n-2;i++)
		for (int j=i+1;j<=n-1;j++)
			{
			    int nr=cauta(j+1,n,v[i]+v[j]);
			    if(nr!=0)
			    s+=nr-j;
			}

	fout<<s<<'\n';

	return 0;
}