Cod sursa(job #1645023)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 10 martie 2016 10:42:52
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int i, j, nr, n, a[805], k;
inline int cauta_binar(int limita){
    int st=j+1, dr=n, mij, sol;
    //a[x]<=limita
    if (a[st]>limita) return st-1;
    if (a[dr]<=limita) return dr;
    sol=0;
    for (mij=st+(dr-st)/2;st<dr;mij=st+(dr-st)/2) {
        if (limita>=a[mij]) {sol=mij; st=mij+1;}
            else dr=mij-1;
    }
    if ((a[st]<=limita)&&(st>sol)) sol=st;
    return sol;
}
int main(){
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d", &n);
    for (i=1;i<=n;i++) scanf("%d", &a[i]);
    sort(a+1, a+n+1); nr=0;
    for (i=1;i<n;i++) for (j=i+1;j<=n;j++) {
        k=cauta_binar(a[i]+a[j]);
        nr+=(k-j);
    }
    printf("%d\n", nr);
    return 0;
}