Cod sursa(job #3370342)

Utilizator Dobre_RaduDobre Radu Dobre_Radu Data 25 octombrie 2026 18:07:32
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

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

int a[803], n;

int CautBins(int l,int y) {
    int r,mid,res;
    r = n-1; res = n;
    while (l <= r) {
        mid = l + (r - l)/2;
        
        if (a[mid] <= y) {
            l = mid + 1;
        } else {
            r = mid - 1;
            res = mid;
        }
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    
    int p,res = 0,s;
    fin >> n;
    for (int i = 0; i < n; i++) fin >> a[i];

    sort(a, a + n);
    
    for (int i = 0;i < n-2;i++) {
        for (int j = i+1;j < n-1;j++){
            s = a[i] + a[j];
            p = CautBins(j + 1,s);
            res += p - j - 1;
        }
    }

    fout << res;
    
    return 0;
}