Cod sursa(job #528375)
#include<fstream.h>
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,v[801],aux[801],c,ok,m,st,dr,nr,poz;
void interclas(int i,int m,int j)
{ int x=i,y=m+1,k=1,t=i;
while(x<=m&&y<=j)
if(v[x]<v[y]) aux[k++]=v[x++];
else aux[k++]=v[y++];
while(x<=m) aux[k++]=v[x++];
while(y<=j) aux[k++]=v[y++];
for(k=1;k<(j-i)+2;k++) v[t++]=aux[k];
}
void divimp(int i,int j)
{ if(i<j)
{int m=i+(j-i)/2;
divimp(i,m);
divimp(m+1,j);
interclas(i,m,j);
}
}
int main()
{ int i,j,k;
f>>n;
for(i=1;i<=n;i++) f>>v[i];
divimp(1,n);
//for(i=1;i<=n;i++) g<<v[i]<<' ';
//g<<'\n';
for(k=3;k<=n;k++)
{j=k-1;
while(j>1)
{c=v[k]-v[j];
st=1; dr=j-1; ok=0;
while(st<=dr&&!ok)
{m=(st+dr)/2;
if(v[m]==c) ok=1,poz=m;
else if(v[m]<c) st=m+1;
else dr=m-1;
}
if(m>=j) m=j-1;
while(v[m]<c&&m<j) m++;
while(v[m-1]>=c&&m>1) m--;
nr=nr+j-m;
/*while(v[m]<=c&&m<j) m++;
while((v[m]>c||m>=j)&&m>0) m--;
nr+=m;*/
//g<<nr<<'\n';
//if(ok) nr+=poz;
/*{i=poz;
while(v[i]==c) nr++,i--;
poz++;
while(v[poz]==c) nr++,poz++;
}*/
j--;
}
}
g<<nr<<'\n';
f.close(); g.close();
return 0;
}