Cod sursa(job #1360542)

Utilizator danalexandruDan Alexandru danalexandru Data 25 februarie 2015 16:02:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int v[801],n;

int bsearch(int x)
{
    int i=0, pas=1<<9;
    while(pas!=0)
    {
        if(i+pas<=n && v[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    return i;
}

int main()
{
    int i,j,s=0,a;
    in>>n;
    for(i=1; i<=n; i++)
        in>>v[i];
    sort(v+1, v+n+1);
    for (i=1; i<=n-2; ++i)
        for (j=i+1; j<=n-1; ++j)
        {
            a = bsearch(v[i] + v[j]);
            if( a > j)
                s += a - j;
        }
    out<<s;

    return 0;
}