Cod sursa(job #1767743)

Utilizator Lungu007Lungu Ionut Lungu007 Data 29 septembrie 2016 17:43:58
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 801
using namespace std;

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

int n,a[NMAX],contor,st,dr,mij,l;

int main()
{
    in >> n;
    for(int i=0;i<n;i++)
    {
        in >> a[i];
    }

    sort(a,a+n);

    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            dr = n-1;
            st = j+1;
            l = -1;
            while(st<=dr)
            {
                mij = (st+dr)/2;
              //  cout << st << " " << dr << "    " << mij << endl;
                if(a[i]+a[j]>=a[mij])
                {
                    l = mij;
                    st = mij+1;
                }
                else
                {
                    dr = mij-1;
                }
                //cout << mij << " ";
            }
           // cout << j << " ";
           if(l!=-1)
            contor += l - j;
        }


    }

    out << contor;
    return 0;
}