Cod sursa(job #2446772)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 10 august 2019 18:14:20
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#define range(x, y, contor) for(int contor = x; contor <= y; contor++)

std::ifstream fin{"nrtri.in"};
std::ofstream fout{"nrtri.out"};

int n, v[801], k, step, nrtri{0}, sum;

int main()
{
    fin>>n;
    range(1, n, i) fin>>v[i];

    std::sort(v + 1, v + n + 1);

    range(1, n-2, i){
        range(i + 1, n - 1, j){
            sum = v[i] + v[j];

            for(step = 1; step < n; step = (step<<1));

            for(k = j; step; step = (step >> 1))
                if(k + step <= n && v[k + step] <= sum) k += step;

            if(k != j) {
               nrtri += (k - j);
            }
        }
    }

    fout<<nrtri;

}