Cod sursa(job #2792399)

Utilizator dotyzebra775Papuc Stefan dotyzebra775 Data 1 noiembrie 2021 16:36:23
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>
#define N 805
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, a[N];

void citire()
{
    int i;
    fin >> n;
    for(i = 1; i <= n; ++ i)
        fin >> a[i];
}

int cb(int p1, int p2, int val)
{
    int st, dr, mij;
    int sol = 0;
    st = p2 + 1; dr = n;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(val >= a[mij])
            {
                st = mij + 1;
                sol = mij;
            }
        else
            dr = mij - 1;
    }
    return sol;
}

int main()
{
    int i, j;
    citire();
    sort(a+1, a+n+1);
    int ct = 0;
    for(i = 1; i <n; ++ i)
        for(j = i + 1; j <= n; ++ j)
        {
            int aux = cb(i, j, a[i] + a[j]);
            if(aux != 0)
               ct += aux - j;
        }
    fout << ct;


    return 0;
}