Cod sursa(job #2911288)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 28 iunie 2022 13:35:57
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda 3_iulie Marime 0.73 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,ap;
int v[850];

void b_search(int suma,int st)
{
    int sst=st;
    int dr=n;
    int poz=-1;
  while(st<=dr)
  {
      int mid=(st+dr)/2;
      if(v[mid]>suma)
      {
          dr=mid-1;
      }
      else
      {
          poz = mid;
          st=mid+1;
      }

  }
  if(poz!=-1)
  {
      ap+=poz-sst+1;
  }

}




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-2;i++)
    {
        for(int j=i+1;j<=n-1;j++)
        {
            b_search(v[i]+v[j],j+1);
        }
    }
    fout<<ap;
}