Cod sursa(job #2079909)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 1 decembrie 2017 23:18:32
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;

void solve() {
    size_t stick_count;
    cin >> stick_count;

    vector< int > lengths(stick_count);
    for (auto& it : lengths)
        cin >> it;

    sort(lengths.begin(), lengths.end());

    int64_t solution = 0;
    for (size_t i = 0; i < stick_count; ++i) {
        for (size_t j = i + 1; j < stick_count; ++j) {
            int sum = lengths[i] + lengths[j] + 1;
            int left = 0, right = (int)stick_count - 1;
            while (left <= right) {
                int middle = (left + right) / 2;
                if (lengths[middle] >= sum)
                    right = middle - 1;
                else
                    left = middle + 1;
            }

            solution += right - (int)j;
        }
    }

    cout << solution << endl;
}

int main() {
    assert(freopen("nrtri.in", "r", stdin));
    assert(freopen("nrtri.out", "w", stdout));
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}