Cod sursa(job #2655706)

Utilizator pupiraresdiRARES DIACONESCU pupiraresdi Data 5 octombrie 2020 11:41:44
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#include <algorithm>

using namespace std;
int v[1000];
int bs_right(int st, int dr, int s){
    int med,last=-1;
    while(st<=dr){
        med=(st+dr)/2;
        if(s>=v[med]){
            last=med;
            st=med+1;
        }else dr=med-1;
    }
    return last;
}
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    int cnt=0,n,i,j,s,poz;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d",&v[i]);
    }
    sort(v+1,v+n+1);
    for(i=1;i<n-1;i++)
        for(j=i+1;j<n;++j)
    {
        s=v[i]+v[j];
        poz=bs_right(j+1,n,s);
        if(poz!=-1){
            cnt+=poz-j;
        }
    }
    printf("%d",cnt);
    return 0;
}