Cod sursa(job #2803245)

Utilizator tedicTheodor Ciobanu tedic Data 19 noiembrie 2021 18:15:25
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include<algorithm>
using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
const int maxn=805;
int v[maxn];
inline int caut_bin_1(int x, int n)
{
    int st=1;
    int dr=n;
    int mij;
    int ans=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>x)
            dr=mij-1;
        else if(v[mij]<=x)
        {
            st=mij+1;
            ans=mij;
        }
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>v[i];
    sort(v+1, v+n+1);
    int rasp=0;
    for(int i=1; i<=n; ++ i)
    for(int j=i+1; j<=n; ++ j)
    {
        int k=caut_bin_1(v[i]+v[j], n);
        if(k!=-1)
            rasp=rasp+k-j;
    }
    cout<<rasp<<'\n';
    return 0;
}