Cod sursa(job #1902881)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 4 martie 2017 20:36:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAX_N = 800;

int v[5 + MAX_N];

int my_binary_search (int st, int dr, int x) {
  int med, last = 0;
  while (st <= dr) {
    med = (st + dr) / 2;
    if (v[med] <= x) {
      st = med + 1;
      last = med;
    }
    else {
      dr = med - 1;
    }
  }
  return last;
}

int main() {
  freopen ("nrtri.in", "r", stdin);
  freopen ("nrtri.out", "w", stdout);

  int N;
  scanf ("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf ("%d", &v[i]);
  }
  sort (v + 1, v + N + 1);
  int nrtri = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
      int poz = my_binary_search (1, N, v[i] + v[j]);
      nrtri += poz - j;
    }
  }
  printf ("%d\n", nrtri);
  return 0;
}