Cod sursa(job #2896083)

Utilizator erixEric stoicescu erix Data 29 aprilie 2022 19:47:12
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int main() {
    int n;
    cin >> n;
    int* arr = new int[n];
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr[i] = x;
    }
    sort(arr, arr + n);
    int cnt = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum = arr[i] + arr[j];
            int l = 0, r = n - 1;
            while (l <= r) {
                int m = (l + r) / 2;
                if (arr[m] <= sum && arr[m + 1] >= sum && m != i && m != j && i != j && m+1<n) {
                    cnt += (n - m + 1) / 3;
                    break;
                }
                else if (arr[m] > sum)
                    r = m - 1;
                else
                    l = m + 1;
            }
        }
    }
    cout << cnt;
    return 0;
}