Cod sursa(job #2337632)

Utilizator cosmin1972Nour Mihai-Cosmin cosmin1972 Data 6 februarie 2019 16:23:42
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>

#include <fstream>

#include <algorithm>

using namespace std;



ifstream in("nrtri.in");

ofstream out("nrtri.out");



int BinarySearch(int low,int high,int k,int v[16001])

{

    int mid,result=-1;

    for(; low<=high;)

    {

        mid=(low+high)/2;

        if(v[mid]<=k)

        {

         if(mid>result)

            result=mid;

         low=mid+1;

        }

        else

            high=mid-1;



    }

    return result;



}



int main()

{

    int v[801];

    int i,j,p,n;

    int x,y,z;

    int sum=0;

    in>>n;

    for(i=0;i<n;i++)

    {

        in>>v[i];

    }

    sort(v,v+n);

    for(i=0;i<n-2;i++)

    {

        for(j=i+1;j<n-1;j++)

        {

            x=BinarySearch(j+1,n-1,v[i]+v[j],v);

            if(x!=-1)

                {

                    sum=sum+x-j;

                }

        }

    }

    out<<sum;

}