Cod sursa(job #1567707)

Utilizator gedicaAlpaca Gedit gedica Data 13 ianuarie 2016 17:52:03
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream>
#include<algorithm>

using namespace std;

const int NMAX= 800;

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

int v[NMAX+5];

int main()
{
    int N, Ans= 0;

    in >> N;

    for( int i= 0; i<N; ++i )
    {
        in >> v[i];
    }

    sort( v, v+N );

    for( int i= 0; i<N-2; ++i )
    {
        for( int j= i+1; j<N-1; ++j )
        {
            int n2, s= v[i]+v[j], pas, sol= j;

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

            for( pas= n2; pas>0; pas/= 2 )
            {
                if ( sol+pas<N && v[sol+pas]<=s )
                    sol+= pas;
            }
            Ans+= sol-j;
        }
    }

    out << Ans << '\n';

    return 0;
}