Cod sursa(job #2337630)

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

using namespace std;

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

int v[803];

int cautbin(int low,int high)
{
        int mid,result=-1,k=v[low]+v[high];

    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 n,sol=0;
    in>>n;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
    }
    sort(v+1,v+n+1);
    for(int i=1;i<=n-2;i++)
    {
        for(int j=i+1;j<=n-1;j++)
        {
            int p = cautbin(i,j);
            if(p!=-1)
                sol+=p-j+1;
        }
    }
    out<<sol;
}