Cod sursa(job #1007995)

Utilizator Athena99Anghel Anca Athena99 Data 9 octombrie 2013 23:34:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

const int nmax=800;

int v[nmax+1];

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

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

    int n2;
    for ( n2= 1; n2<=n; n2*= 2 ) {
    }

    int sol= 0;
    for ( int i= 1; i<=n-2; ++i ) {
        for ( int j= i+1; j<=n-1; ++j ) {
            int aux= 1, step;
            for ( step= n2; step; step/= 2 ) {
                if ( aux+step<=n && v[aux+step]<=v[i]+v[j] ) {
                    aux+= step;
                }
            }

            //printf("%d %d             %d %d %d\n", i, j, v[i], v[j], aux);
 
            sol+= aux-j;
        }
    }

    fout<<sol<<"\n";

    return 0;
}