Cod sursa(job #2184111)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 23 martie 2018 18:51:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int L = 8 ;
int v[800] ;
int cnt ,n ;
int cautbin ( int x )
{
    int r = 0, pas = 1<<L;
    while ( pas!= 0 )
    {
        if ( r + pas < n && v[r + pas] <= x )
        {
            r += pas;
        }
        pas /= 2;
    }
    return r;
}
int main()
{
    freopen("nrtri.in","r",stdin) ;
    freopen("nrtri.out","w",stdout) ;
    int i ,j ,k ,sum ;
    scanf("%d",&n) ;
    for (i = 1 ; i <= n ; ++ i){
        scanf("%d",&v[i]) ;
    }
    sort(v + 1 ,v + 1 + n) ;
    for (i = 1 ; i <= n ; ++ i){
        for (j = i + 1 ; j <= n ; ++ j){
            sum = v[i] + v[j] ;
            k = cautbin(sum) ;
            if (k > j)
                cnt += k - j + 1 ;
        }
    }
    printf("%d",cnt) ;
    return 0;
}