Cod sursa(job #3300554)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 16 iunie 2025 23:49:07
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_DIM = 800;

int a[MAX_DIM + 1], n;
int64_t cnt;

int main() {
   fin >> n;
   for (int i = 1; i <= n; i++)
      fin >> a[i];
   
   sort(a + 1, a + 1 + n);
   cnt = 0;
   
   for (int i = 1; i < n - 1; i++)
      for (int j = i + 1; j < n; j++) {
         int st = j + 1, dr = n, mid, pos = 0;
         bool ok = 0;
         while (st <= dr) {
            mid = (st + dr) >> 1;
            if (a[i] + a[j] >= a[mid]) {
               pos = st;
               st = mid + 1;
               ok = 1;
            } else
               dr = mid - 1;
         }
         if (ok)
            cnt += (pos - j);
      }
      
   fout << cnt << "\n";
   
   fin.close();
   fout.close();
   return 0;
}