Cod sursa(job #3324394)

Utilizator iustin251007iustin balint iustin251007 Data 22 noiembrie 2025 10:29:43
Problema Numarare triunghiuri Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");

    int N;
    fin >> N;
    vector<int> sticks(N);
    for (int i = 0; i < N; ++i) fin >> sticks[i];

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

    long long count = 0;

    for (int i = 0; i < N - 2; ++i) {
        for (int j = i + 1; j < N - 1; ++j) {
            int sum = sticks[i] + sticks[j];

            // Cautam k maxim cu sticks[k] <= sum
            int left = j + 1, right = N - 1, pos = j;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (sticks[mid] <= sum) {
                    pos = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            count += (pos - j); // toate segmentele de la j+1 la pos
        }
    }

    fout << count << endl;
    return 0;
}