Cod sursa(job #2035310)

Utilizator SilasiMariusSilasi Marius-Adrian SilasiMarius Data 9 octombrie 2017 10:40:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <algorithm>

std::ifstream fin("nrtri.in");
std::ofstream fout("nrtri.out");

int n, a[801];

int Search(int l, int r, int s);

int main()
{
    bool sortat;
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
    std::sort(a + 1, a + 1 + n);
    int rez{0};
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            rez += Search(j + 1, n, a[i] + a[j]);

    fout << rez << '\n';
}

int Search(int l, int r, int s)
{
    int m, p{-1}, pi{l};
    while (l <= r)
    {
        m = (l + r) / 2;
        if (a[m] <= s)
            l = m + 1, p = m;
        else
            r = m - 1;
    }

    if (p == -1)
        return 0;
    else
        return p - pi + 1;
}