Cod sursa(job #3299486)

Utilizator batasAndrei Batis batas Data 7 iunie 2025 09:19:43
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

struct Dublet {
    int i;
    int j;
    int val;
};

int CautareBinara(int val, int start);

const int DIM = 805;
int bete[DIM];
Dublet sume[DIM * DIM + 1];
int n, m;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; ++i)
        fin >> bete[i];

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

    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
        {
            sume[++m].i = i;
            sume[m].j = j;
            sume[m].val = bete[i] + bete[j];
        }

    int ans(0);

    for (int i = 1; i <= m; ++i)
    {
        int rez = CautareBinara(sume[i].val, sume[i].j + 1);

        if (rez != -1)
            ans += (rez - (sume[i].j + 1) + 1);
    }

    fout << ans;

    return 0;
}

int CautareBinara(int val, int start)
{
    int st(start), dr(n), mij, rez(-1);

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

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

    return rez;
}