Cod sursa(job #2233421)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 23 august 2018 11:31:24
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#include <algorithm>

const int NMAX = 800 + 5;
FILE *fin = freopen("nrtri.in","r",stdin); FILE *fout = freopen("nrtri.out","w",stdout);

/* ======= DATA ========= */
int n, v[NMAX];
/* ======= DATA ========= */

int cb(int val)
{
    int pas= 1, k= 0;
    for(; pas <= n; pas<<=1);
    for(; pas; pas >>=1)
    {
        if(k+pas<= n && v[k+pas]<= val)
            k+=pas;
    }
    return k;
}

void Rezolva()
{
    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);
}

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

    Rezolva();
}