Cod sursa(job #2807520)

Utilizator hoprixVlad Opris hoprix Data 23 noiembrie 2021 21:24:09
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;

int v[800];

int bsearch(int st, int dr, int val) {
    int m, p = -1;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (v[m] <= val) {
            p = m;
            st = m+1;
        }
        else dr = m-1;
    }
    return p;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    
    int n, x; fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i];

    sort(v, v+n);

    int moduri = 0;
    for (int i = 0; i < n-2; i++)
        for (int j = i+1; j < n-1; j++) {
            int p = bsearch(j+1, n-1, v[i]+v[j]);
            if (p != -1)
                moduri += p-j;
        }
    fout << moduri;
    
    return 0;
}