Cod sursa(job #2547440)

Utilizator OvidRata Ovidiu Ovid Data 15 februarie 2020 12:55:02
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ft first
#define sc second

ifstream fin("nrtri.in"); ofstream fout("nrtri.out");
int n, a[1000];


int bs(int x, int y, int l, int r){
int m=(l+r)/2;

if(l>r){return -1;}

if(l==r){
    if( (a[m]+x)>=y ){return m;}
    else{return -1;}
}



if( (a[m]+x)<y ){
    return bs(x, y, m+1, r);
}

if( (a[m]+x)>=y ){
    return bs(x, y, l, m);
}


}







int main(){
fin>>n;

for(int i=0; i<n; i++){
    fin>>a[i];
}
sort(a, a+n);



int rez=0;
for(int i=0; i<(n-2); i++){
    for(int j=i+2; j<n; j++){
        int g=bs(a[i], a[j], i+1, j-1);
        if(g<0){continue;}
        rez+=j-g;
    }
}


fout<<rez;
return 0;
}