Cod sursa(job #2633613)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 7 iulie 2020 21:53:54
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, cnt, a[805];

int main () {
  fin >> n;
  for (int i = 1 ; i <= n ; i ++)
    fin >> a[i];
  sort (a + 1, a + n + 1);
  for (int i = 1 ; i <= n - 2; i ++)
    for (int j = i + 1 ; j < n; j ++) {
      int st = j + 1, dr = n , k = n;
      while (st <= dr) {
        k = (st + dr) / 2;
        if (a[i] + a[j] >= a[k])
          st = k + 1;
        else
          dr = k - 1;
      }
      cnt += (dr - j);
    }
  fout << cnt;
  return 0;
}