Cod sursa(job #3324464)

Utilizator AlekuwAlexandru Stefan Pascut Alekuw Data 22 noiembrie 2025 10:59:41
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
#define NMAX 801
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");

int main() {
    int n, v[NMAX];
    in >> n;
    for (int i = 0; i < n; ++i)
        in >> v[i];
    sort(v, v + n);
    long long cnt = 0;
    for (int i = 0; i < n - 2; ++i)
        for (int j = i + 1; j < n - 1; ++j) {
            int s = v[i] + v[j];
            int low = j + 1, high = n - 1, r = j;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (v[mid] <= s){
                    r = mid;
                    low = mid + 1;
                }
                else
                    high = mid - 1;
            }
            cnt += (r - j);
        }
    out << cnt;
    return 0;
}