Cod sursa(job #2184115)

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

const int L = 9 ;
int v[801] ;
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 - 2 ; ++ i){
        for (j = i + 1 ; j <= n - 1 ; ++ j){
            sum = v[i] + v[j] ;
            k = cautbin(sum) ;
            if (k > j)
                cnt += k - j ;
        }
    }
    printf("%d",cnt) ;
    return 0;
}