Cod sursa(job #2891352)

Utilizator hobbitczxdumnezEU hobbitczx Data 18 aprilie 2022 12:05:32
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 1e3 + 5;

int a[N_MAX] , n , cnt;

int main(){
    ios_base::sync_with_stdio(false);
    fin >> n;
    for (int i=1; i<=n; i++){
        fin >> a[i];
    }
    sort(a + 1 , a + n + 1);
    for (int i=1; i<n-1; i++){
        for (int j=i+1; j<n; j++){
            int st = j + 1 , dr = n;
            while (st <= dr){
                int mij = (st + dr) / 2;
                if (a[mij] > a[i] + a[j]){
                    dr = mij - 1;
                }
                else{
                    st = mij + 1;
                }
            }
            cnt += (dr - j);
        }
    }
    fout << cnt;
}