Cod sursa(job #2973648)

Utilizator AndreiBadAndrei Badulescu AndreiBad Data 1 februarie 2023 15:24:53
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
//
//  main.cpp
//  Numarare triunghiuri (infoarena)
//
//  Created by Andrei Bădulescu on 01.02.23.
//

//#include <iostream>
#include <fstream>

using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

const int N = 800;

short int sticks[N + 1];
int n, a, b;

int bSearch(int lhs, int rhs) {
    int result = 0;
    int mid;

    while (lhs <= rhs) {
        mid = (lhs + rhs) / 2;

        if (sticks[mid] <= a + b) {
            result = mid;
            lhs = mid + 1;
        } else {
            rhs = mid - 1;
        }
    }

    return result;
}

int main() {
    cin >> n;

    for (auto i = 1; i <= n; i++) {
        cin >> sticks[i];
    }

    sort(sticks + 1, sticks + n + 1);

    long long result = 0;

    for (auto i = 1; i < n; i++) {
        for (auto j = i + 1; j <= n; j++) {
            a = sticks[i];
            b = sticks[j];
            result += bSearch(1, n) - j;
        }
    }

    cout << result;
    return 0;
}