Cod sursa(job #3141291)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 13 iulie 2023 14:31:49
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <algorithm>

using namespace std;
const int NMAX = 800;
const int LOGMAX = 9;

int a[NMAX + 1];

int main ()
{
    freopen("nrtri.in" , "r" , stdin);
    freopen("nrtri.out" , "w" , stdout);
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1 , a + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            int high = a[i] + a[j]; // upper bound

            int indexHigh = 0;
            for (int bit = LOGMAX; bit >= 0; bit--)
            {
                indexHigh += (1 << bit);
                if (indexHigh > n || a[indexHigh] > high) indexHigh -= (1 << bit);
            }
            
            int total = indexHigh - j;
        //    cout << total << '\n';
             
            if (total > 0) 
                ans += total;
        }
    }
    cout << ans << '\n';
}