Cod sursa(job #2407206)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 16 aprilie 2019 17:42:31
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, v[801], s, st, dr, mid, sol, poz;

int main (){

      fin>>n;

      for(int i=1; i<=n; i++)
            fin>>v[i];
      sort(v+1,v+1+n);

      for(int i=1; i<n-1; i++)
            for(int j=i+1; j<n; j++){

                  s=v[i] + v[j];

                  st=j+1;
                  dr=n;

                  while(st <= dr){

                        mid=(st + dr)/2;

                        if(v[mid] <= s)
                              st=mid+1;
                        else
                              dr=mid-1;
                  }

                  sol=sol + dr - j;
            }

      fout<<sol;

      return 0;
}