Cod sursa(job #2010763)

Utilizator Constantin.Dragancea Constantin Constantin. Data 14 august 2017 12:16:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <bits/stdc++.h>
using namespace std;

int n,A[810],ans;

int caut(int a, int b){
    int l=b+1,r=n,m,val=A[a]+A[b];
    while (l<=r){
        m=(l+r)/2;
        if (val<A[m]) r=m-1;
        else l=m+1;
    }
    return r-b;
}

int main(){
    ifstream cin ("nrtri.in");
    ofstream cin ("nrtri.out");
    cin>>n;
    for (int i=1; i<=n; i++) cin>>A[i];
    sort(A+1,A+1+n);
    for (int i=1; i<n-1; i++){
        for (int j=i+1; j<n; j++) ans+=caut(i,j);
    }
    cout<<ans;
    return 0;
}