Cod sursa(job #2885738)

Utilizator dfettiDaniel Fetti dfetti Data 6 aprilie 2022 14:55:51
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

#define DIM 801

int n;
int A[DIM];

int bs(int lo, int hi, long long x);

void sort()
{
    int aux;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (A[i] > A[j])
            {
                aux = A[i];
                A[i] = A[j];
                A[j] = aux;
            }
        }
    }
}

int main()
{
    fin >> n;
    for (int i = 0; i < n; ++i)
    {
        fin >> A[i];
    }

    sort();

    int count = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            for (int k = j + 1; k < n && A[i] + A[j] >= A[k]; ++k)
                count++;
    fout << count;

    return 0;
}


int bs(int lo, int hi, long long x)
{
    while (hi - lo > 1)
    {
        int med = (hi + lo) / 2;

        if (x < A[med])
            hi = med;
        else
            lo = med;
    }

    return lo;
};