Cod sursa(job #1489619)

Utilizator ancabdBadiu Anca ancabd Data 21 septembrie 2015 18:52:04
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int a[860], n, nr;

int main()
{
    fin >> n;

    for (int i=1;i<=n;i++)fin >> a[i];

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

    int sm,st,dr,mij;

    for (int i=1;i <= n - 2;i++)
    {
        for (int j = i + 1; j <= n-1;j++)
        {
            sm=a[i]+a[j];

            st=max(i,j);
            dr=n;

            while (st < dr)
            {
                mij=(st+dr)/2;
                if (a[mij] > sm) dr = mij - 1;
                if (a[mij] <= sm) st = mij + 1;
            }
            mij =(st + dr)/2;
            if (a[mij] > sm) mij--;
            nr += mij - max(i, j);

        }
    }
    fout << nr;
    return 0;

}