Cod sursa(job #2753415)

Utilizator darrenRares Buhai darren Data 22 mai 2021 20:24:11
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <algorithm>

using namespace std;

int N;
int A[800];

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

    fin >> N;
    for (int i = 0; i < N; i++)
        fin >> A[i];
    
    sort(A, A + N);

    int count = 0;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
        {
            int lo = j, hi = N - 1;
            while (lo < hi)
            {
                int mid = (lo + hi + 1) / 2;
                if (A[mid] <= A[i] + A[j])
                    lo = mid;
                else
                    hi = mid - 1;
            }
            count += lo - j;
        }

    fout << count << '\n';

    fin.close();
    fout.close();
}