Cod sursa(job #2795702)

Utilizator mariaionescu2006Ionescu Maria mariaionescu2006 Data 6 noiembrie 2021 20:02:34
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int v[801],n,k;
int main()
{
    fin >>n;
    for (int i=1;i<=n;i++)
        {fin >>v[i];}
    sort(v+1,v+n+1);
    for (int i=1;i<n;i++)
        {for (int j=i+1;j<n;j++)
             {int st=j+1,dr=n,sol=-1;
              while (st<=dr)
                    {int mij=(st+dr)/2;
                     if (v[i]+v[j]>=v[mij]) {sol=mij;
                                             st=mij+1;}
                     else dr=mij-1;}
              if (sol!=-1) k=k+sol-j;}}
    fout <<k;
    return 0;
}