Cod sursa(job #2678075)

Utilizator bibiancapitu2004Pitu Bianca bibiancapitu2004 Data 28 noiembrie 2020 09:03:14
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include<algorithm>
using namespace std;

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

int l[805] , n;
int upperBound(int target)
{
    int s = 0,h = n ;
  while(s < h)
  {
      int mid = (s + h) / 2;
      if(l[mid] > target)
        h = mid;
      else s = mid + 1;
  }
  return h;
}



int main()
{
    int nr = 0;
    in >> n;
    for(int i = 0;i < n;i ++)
        in >>l[i];
    sort(l,l + n);
    for(int i = 0;i <n - 2;i ++)
    {
        for(int j = i + 1;j < n - 1 ;j ++)
        {
            int x = upperBound(l[i] + l[j]) - 1;

            nr += x - j;

        }
    }
    out << nr;


    return 0;
}