Cod sursa(job #3142516)

Utilizator matyaskrizbaiKrizbai Matyas matyaskrizbai Data 22 iulie 2023 08:36:14
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

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

int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n;
   fin >> n;
   vector<int> v(n);
   for(auto& val : v)
      fin >> val;
   sort(v.begin(), v.end());
   int cnt=0;
   for(int i=0; i<n; i++){
      for(int j=i+1; j<n; j++){
         int x=v[i]+v[j];
         int st=0, dr=n-1, mid;
         while(st<=dr){
            mid=(st+dr)/2;
            if(x<v[mid])
               dr=mid-1;
            else
               st=mid+1;
         }
         if(dr-j>0)
            cnt+=dr-j;
      }
   }
   fout << cnt;
   return 0;
}