Cod sursa(job #2080865)

Utilizator xkz01X.K.Z. xkz01 Data 3 decembrie 2017 16:27:44
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int i, j, n, a[802], st, dr, mij, nrtri;
int main(){
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d", &n); nrtri=0;
    for (i=1;i<=n;++i) scanf("%d", &a[i]);
    sort(a+1, a+n+1);
    for (i=1;i<n;++i) for (j=i+1;j<=n;++j) {
        st=1; dr=n;
        while (st<=dr) {
            mij=st+(dr-st)/2;
            if (a[mij]>=a[i]+a[j]+1) dr=mij-1; else st=mij+1;
        }
        nrtri+=dr-j;
    }
    printf("%d\n", nrtri);
    return 0;
}