Pagini recente » Cod sursa (job #1281522) | Cod sursa (job #2232761) | moisil2018 | Cod sursa (job #2278978) | Cod sursa (job #285443)
Cod sursa(job #285443)
#include<stdio.h>
int n;
long v[1010];
void read()
{
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%ld",&v[i]);
v[++n]=999999999;
}
int part(int st, int dr)
{
int i,j,m;
long p,aux;
m=(st+dr)>>1;
p=v[m];
i=st-1;
j=dr+1;
while(1)
{
do{++i;}while(v[i]<p);
do{--j;}while(v[j]>p);
if(i<j)
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
else
return j;
}
}
void quick(int st, int dr)
{
int p;
if(st<dr)
{
p=part(st,dr);
quick(st,p);
quick(p+1,dr);
}
}
int cautare(long x,long poz)
{
int st=poz,dr=n,m;
if(v[poz]>=x)
return poz;
while(st!=dr)
{
m=(st+dr)>>1;
if(x<=v[m])
dr=m;
else
st=m+1;
}
return st;
}
void rez()
{
int i,j;
long s=0;
for(i=1;i<=n-3;i++)
for(j=i+1;j<=n-2;j++)
s=s+(cautare(v[i]+v[j]+1,j+1)-1-j);
printf("%ld\n",s);
}
int main()
{
read();
quick(1,n);
rez();
return 0;
}