Cod sursa(job #2872688)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 17 martie 2022 17:58:14
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <algorithm>
#define NMAX 800
using namespace std;

int v[NMAX + 1], n;


int main(){

  ifstream fin ("nrtri.in");
  ofstream fout ("nrtri.out");
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> v[i];
  sort (v + 1, v + n + 1);

  int sol = 0;
  for (int i = 1; i <= n - 2; i++){
    for (int j = i + 1; j <= n - 1; j++){

      int st = j, pas = (1 << 15);
      while (pas != 0){
        if (st + pas <= n && v[st + pas] <= v[i] + v[j])
          st += pas;
        pas /= 2;
      }


      sol += st - j;
    }
  }
  fout << sol;
  return 0;
}