Cod sursa(job #2288014)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 22 noiembrie 2018 19:22:07
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <algorithm>

FILE *fin = freopen("nrtri.in","r",stdin);
FILE *fout = freopen("nrtri.out","w",stdout);

static const int NMAX = 805;

int n;
int v[NMAX];

int cb(int x)
{
    int logN=1,k=0;
    for(;logN<=n;logN<<=1);

    for(; logN ; logN >>=1)
    {
        if(logN + k <= n)
        {
            if(v[logN+k] <= x)
                k+=logN;
        }
    }
    return k;
}

void Solve()
{
    int ct =0;
    for(int i = 1; i< n; ++i)
    {
        for(int j = i + 1; j<= n; ++j)
        {
            int x = cb(v[i]+v[j]);
            ct += (x - j);
        }
    }
    printf("%d",ct);
}

void ReadInput()
{
    scanf("%d",&n);
    for(int i = 1;i<=n ; ++i)
        scanf("%d",&v[i]);
    std::sort(v+1,v+n+1);
}

int main()
{
    ReadInput();
    Solve();
}