Cod sursa(job #2911096)

Utilizator anghelpatrickPatrick Anghel anghelpatrick Data 26 iunie 2022 19:47:17
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda 3_iulie Marime 0.69 kb
#include <iostream>
#include <algorithm>

using namespace std;

int v[1002],i,j,cnt=0,n;


void bin_search (int i, int j)
{
    int mij = 0;
    int st = j + 1 ;
    int dr = n ;
    while( st <= dr )
    {
        mij = (st+dr) / 2 ;
        int s = v[i] + v[j] ;
        if( v[mij] > s )
            dr = mij-1;
        else
            st = mij+1;
    }

    cnt += dr - j
}

int main()
{
    cin >> n;
    for( i = 1 ; i <= n ; i ++ )
        cin >> v[i] ;

    sort( v+1 , v+n+1 );

    for( i = 1 ; i <= n - 1  ; i ++ )
    {
        for( j = i + 1 ; j <= n ; j ++ )
        {
            bin_search(i,j) ;
        }
    }
    cout << cnt ;
    return 0;
}