Cod sursa(job #1418487)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 13 aprilie 2015 12:01:12
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, A[801];
int lo, hi, mid, cnt;

int main()
{
    fin >> n;
    for( int i = 1; i <= n; ++i )
        fin >> A[i];
    sort( A + 1, A + 1 + n );
    for( int i = 1; i < n - 1; ++i )
        for( int j = i + 1; j <= n; ++j )
        {
            lo = j + 1, hi = n;
            while( lo <= hi )
            {
                mid = (lo + hi) / 2;
                if( A[i] + A[j] >= A[mid] )
                    lo = mid + 1;
                else
                    hi = mid - 1;
            }
            cnt += hi - j;
        }
    fout << cnt;
    return 0;
}