Cod sursa(job #3002415)

Utilizator 55andreiv55Andrei Voicu 55andreiv55 Data 14 martie 2023 18:59:12
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>

using namespace std;
const int N = 801;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int n, v[N];

int bin_sc(int val)
{
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr)
    {
        int m = (st + dr) / 2;
        if (v[m] <= val)
        {
            rez = m;
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    return rez;
}

int main()
{
    int s = 0;
    in >> n;
    for (int i = 0; i < n; i++)
        in >> v[i];
    sort(v, v + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            s += bin_sc(v[i] + v[j]) - j;
        }
    }
    out << s;
    return 0;
}