Cod sursa(job #1207662)

Utilizator ZenusTudor Costin Razvan Zenus Data 13 iulie 2014 15:46:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 1000

int ans,N,i,j,right,left,final,mid;
int A[NMAX];

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);

for (i=1;i<=N-2;++i)
for (j=i+1;j<=N-1;++j)
{
    left=1,right=N,final=0;

    while (left<=right)
    {
        mid=(left+right)>>1;

        if (A[mid]<=A[i]+A[j])
        {
            final=mid;
            left=mid+1;
            continue;
        }
        right=mid-1;
    }

    ans+=final-j;
}

printf("%d\n",ans);

return 0;
}