Cod sursa(job #472880)

Utilizator SpiderManSimoiu Robert SpiderMan Data 26 iulie 2010 21:50:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
# include <algorithm>
using namespace std;

const char FIN[] = "nrtri.in", FOU[] = "nrtri.out" ;

int V[805] ;
int N, sol ;

inline int cb ( int val ) {
    int rez = 0 ;

    for ( int st = 0, dr = N; st <= dr; ) {
        int mij = st + ( ( dr - st ) >> 1 ) ;
        if ( V[mij] <= val ) {
            rez = mij, st = mij + 1 ;
        } else {
            dr = mij - 1;
        }
    }

    return rez ;
}

int main() {
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    scanf ( "%d", &N ) ;

    for ( int i = 1; i <= N; ++i ) {
        scanf ( "%d", &V[i] ) ;
    }

    sort ( V + 1, V + N + 1 ) ;

    for ( int i = 1; i < N; ++i ) {
        for ( int j = i + 1; j <= N; ++j ) {
            sol += cb ( V[i] + V[j] ) - j ;
        }
    }

    printf ( "%d", sol ) ;

    return 0;
}