Cod sursa(job #1725782)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 6 iulie 2016 14:26:00
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<bits/stdc++.h>
using namespace std;
int n,v[805],l,ls,ld,sol,m,nrtri;
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    sort(v+1,v+n+1);
    for(int i=1;i<=(n-2);i++)
    {
        for(int j=(i+1);j<=(n-1);j++)
        {
            l=v[i]+v[j]-1;
            ls=j+1;
            ld=n;
            sol=0;
            while (ls<ld)
            {
                m=ls+(ld-ls)/2;
                if (v[m]<=l)
                {
                    sol=m;
                    ls=m+1;
                }
                    else ld=m-1;
            }
            if (sol) nrtri=nrtri+sol-i;
        }
    }
    printf("%d\n",nrtri);
    return 0;
}