Cod sursa(job #2657752)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 11 octombrie 2020 21:07:06
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int bin(int st, int dr, int val)
{
    int last = -1;

    while (st <= dr)
    {
        int mij = (st + dr) / 2;

        if (v[mij] <= val)
        {
            last = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }

    return last;
}

int main()
{
    ifstream in("nrtri.in");
    ofstream out("nrtri.out");
    int n;
    int sol = 0;

    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> v[i];
    }

    sort(v + 1, v + 1 + n);

    for (int i = 1; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int poz = bin(j + 1, n, v[i] + v[j]);
            if (poz != -1)
            {
                sol += (poz - j);
            }
        }
    }

    out << sol << '\n';

    return 0;
}