Cod sursa(job #1742967)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 17 august 2016 13:18:33
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout("nrtri.out");
using namespace std;
int n,v[1000],sum,crt,rsp,i,j,cs,cd,mij;
int main()
{
    fin>>n;
    for( i = 1 ; i <= n ; i++ )
        fin>>v[ i ];
    sort( v + 1 , v + n + 1 );
    for( i = 1 ; i <= n ; i++ )
    {
        for( j = i + 1 ; j <= n ; j++ )
        {
            crt = 0;
            sum = v[ i ] + v[ j ];
            cs = j + 1;
            cd = n;
            while( cs <= cd )
            {
                mij = ( cs + cd ) >> 1;
                if( v[ mij ] <= sum )
                {
                    crt = mij;
                    cs = mij + 1;
                }
                else
                    cd = mij - 1;
            }
            rsp = rsp + max( crt , j ) - j;
        }
    }
    fout<<rsp;
}