Cod sursa(job #3324472)

Utilizator octavianioan_15Gainaru Octavian octavianioan_15 Data 22 noiembrie 2025 11:11:43
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 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;
}