Cod sursa(job #2837095)

Utilizator David0911David Teregovan David0911 Data 21 ianuarie 2022 18:50:01
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[802], nr = 0, st, dr, m, n;
void cautbin(int x, int y)
{
    st = y + 1;
    dr = n;
    while( st <= dr)
    {
            m = (st + dr) / 2;


        if ( v[m] > v[x] + v[y])
        {
            dr = m - 1;
        }
        else
        {
            st = m + 1;
        }
    }
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1 ; j <= n; j++)
        {
            cautbin(i, j);
            nr += dr - j;
            /*if(dr - j  > 0)
            {
                cout << i << j << '\n';
            }*/
        }
    }
    fout << nr;
    return 0;
}