Cod sursa(job #2961904)

Utilizator popica312Pop David-Gabriel popica312 Data 7 ianuarie 2023 12:49:53
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

int N, v[800], i, total;

int caut_binar(int sum, int j, int st, int dr)
{
     while (st <= dr)
     {
         int mij = (st + dr) / 2;
         if (sum >= v[mij])
         {
              st = mij + 1;
         }
         else
         {
              dr = mij - 1;
         }
     }
     return dr - j;
}

int main()
{
     cin >> N;
     for (i = 0; i < N; ++i)
     {
         cin >> v[i];
     }
     sort (v, v+N);
     for (i = 0; i < N - 2; ++i)
     {
          for (int j = i + 1; j < N - 1; ++j)
          {
               int sum = v[i] + v[j];
               total = total + caut_binar(sum, j, j+1, N-1);
          }
     }
     cout << total;
     return 0;
}