Cod sursa(job #2259301)

Utilizator pofianFilipp pofian Data 13 octombrie 2018 11:24:44
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,a[805],sol;

void cit()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    sort(a+1,a+n+1);
}

int gas(int i1,int j1,int s)
{
    if(i1==j1)
    {
        if(s>=a[i1])
            return i1;
        else
            return 0;
    }
    if(a[i1]>s)
        return 0;
    int med=(i1+j1)/2;
    return max(gas(i1,med,s),gas(med+1,j1,s));
}

int main()
{
    int i,j,r;
    cit();
    for(i=1;i<=n-2;i++)
    for(j=i+1;j<=n-1;j++)
    {
        r=gas(j+1,n,a[i]+a[j]);
        if(r)
            sol+=(r-j);
    }
    fout<<sol;
}