Cod sursa(job #2702257)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 3 februarie 2021 13:54:18
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#define NMAX 2000
#define LMAX 30000

using namespace std;

unsigned short lungimi[LMAX+1], bete[NMAX+1];

int main()
{
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    int n, k, nrtri, j;
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        fin >> j;
        lungimi[j]++;
    }
    n = 0;
    for (int i = 1; i <= LMAX; i++)
    {
        for (int j = lungimi[i]; j > 0; j--)
        {
            bete[n++] = i;
        }
    }
    nrtri = 0;
    for (int i = 0; i < n - 2; i++)
    {
        k = i + 2;
        for (int j = i + 1; j < n - 1; j++)
        {
            while (k < n && bete[i] + bete[j] > bete[k])
            {
                k++;
            }
            nrtri += k - j - 1;
        }
    }
    fout << nrtri;

    return 0;
}