Cod sursa(job #3265526)

Utilizator KLNNNDanaila Calin KLNNN Data 30 decembrie 2024 22:02:07
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

int bin_search(int x, int y, int n, int v[])
{
    int st = y + 1, dr = n - 1;
    
    while (st <= dr) {
        int mij = st + (dr - st) / 2;
        
        if (v[mij] > v[x] + v[y])
            dr = mij - 1;
        else st = mij + 1;
    }
    
    return dr;
    
}

int main(void)
{
    ifstream cin("nrtri.in");
    ofstream cout("nrtri.out");
    
    int n, v[100001], nr = 0, dr;
    cin >> n;
    
    for (int i = 0; i < n; i++)
        cin >> v[i];
        
    sort(v, v + n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            dr = bin_search(i, j, n, v);
            nr += dr - j;
        }
    }
    
    cout << nr;

    return 0;
}