Cod sursa(job #2612137)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 8 mai 2020 15:28:11
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

auto count(std::vector<int>& v) -> int
{
    int count{ 0 };

    for(auto rightmost = v.size() - 1; rightmost >= 2; --rightmost) {
        int left{ 0 };
        int right{ static_cast<int>(rightmost) - 1 };

        while(left < right) {
            auto const l = v[static_cast<std::size_t>(left)];
            auto const r = v[static_cast<std::size_t>(right)];

            if(l + r >= v[rightmost]) {
                count += (right - left);
                --right;
            }
            else {
                ++left;
            }
        }
    }

    return count;
}

auto main() noexcept -> int
{
    std::ifstream f{ "nrtri.in" };
    std::ofstream g{ "nrtri.out" };

    int num{ 0 };
    std::vector<int> nums{};

    f >> num;
    nums.reserve(static_cast<std::size_t>(num));

    for(int i = 0; i < num; ++i) {
        int x{ 0 };
        f >> x;
        nums.push_back(x);
    }

    std::sort(nums.begin(), nums.end());
    std::cout << count(nums) << std::endl;
}