Cod sursa(job #3240823)

Utilizator SilviuC25Silviu Chisalita SilviuC25 Data 21 august 2024 11:26:20
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    fin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        fin >> arr[i];
    }
    int answer = 0;
    sort(arr.begin(), arr.end());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int left = j + 1, right = n - 1, target = arr[i] + arr[j];
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] <= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            answer += right - j;
        }
    }
    fout << answer;
    return 0;
}