Cod sursa(job #1372934)

Utilizator apostolandreiApostol Andrei Laurentiu apostolandrei Data 4 martie 2015 15:52:04
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[10001], n;
int cautare_binara(int x){
  int i = 0;
  int pos = 1 << 16;
  while (pos != 0) {
    if(i + pos <= n && v[i + pos] <= x)
      i += pos;
    pos /= 2;
  }
  return i;
}
int main()
{
    int nr = 0;
    in >> n;
    for (int i = 1; i <= n; i++) in >> v[i];
    sort (v + 1, v + n + 1);
    for (int i = 1; i <= n - 2; i ++)
      for (int j = i + 1; j <= n - 1; j++){
        int z = cautare_binara(v[i] + v[j]);
        if (z > j) nr += z - j;
      }
    out << nr;
}