Cod sursa(job #2435342)

Utilizator Alex_DiaconuDiaconu Alexandru Alex_Diaconu Data 3 iulie 2019 17:59:57
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int nmax=800;
int v[nmax+1];

ifstream ci ("nrtri.in");
ofstream co ("nrtri.out");

int main ()
{
    int n,n2=1;
    ci >> n;
    while (n2*2<=n)
    {
        n2*=2;
    }
    for (int i=1; i<=n; i++)
    {
        ci >> v[i];
    }
    sort (v+1,v+n+1);
    int sol=0;
    for (int i=1; i<n-1; i++)
    {
        for (int j=i+1; j<n; j++)
        {
            int k=j;
            for (int step=n2; step>0; step/=2)
            {
                if (k+step<=n && v[k+step]<=v[i]+v[j])
                {
                    k+=step;
                }
            }
            sol+=k-j;
        }
    }
    co << sol;
    return 0;
}