Cod sursa(job #2338823)

Utilizator cosmin1972Nour Mihai-Cosmin cosmin1972 Data 7 februarie 2019 20:56:09
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 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;



}