Cod sursa(job #2232993)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 21 august 2018 20:33:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 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 st  = 1, dr = n , res = -1;
    while(st<= dr)
    {
        int mij = (st + dr) >> 1;
        if(v[mij] <= val)
        {
            st = mij + 1;
            res = mij;
        }
        else
            dr = mij - 1;
    }
    return res;
}

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