Pagini recente » Cod sursa (job #2536167) | Cod sursa (job #2498166) | Cod sursa (job #1713556) | Cod sursa (job #1795460) | Cod sursa (job #895410)
Cod sursa(job #895410)
#include <cstdio>
#include <algorithm>
#define NMax 30001
using namespace std;
long n,vmin[NMax+NMax],vmax[NMax+NMax],v[NMax],minn,maxx,rez;
int bsearchMin(long in,long fn,long v[],long val) {
long mid;
if(v[fn]<=val)
return fn;
else
if(val<v[1])
return 0;
while(in<=fn) {
mid=(fn-in)/2+in;
if(v[mid]<=val&&val<v[mid+1])
return mid;
else
if(val<v[mid])
fn=mid-1;
else
in=mid+1;
}
return 0;
}
int bsearchMax(long in,long fn,long v[],long val) {
long mid;
if(v[fn]<val)
return 0;
else
if(val<=v[1])
return 1;
while(in<=fn) {
mid=(fn-in)/2+in;
if(v[mid]>=val&&val>v[mid-1])
return mid;
else
if(val<v[mid])
fn=mid-1;
else
in=mid+1;
}
return 0;
}
bool comp(long a,long b) {
if(a<=b)
return 1;
return 0;
}
int main()
{
freopen("nrtri.in","rt",stdin);
freopen("nrtri.out","wt",stdout);
scanf("%ld",&n);
for(long i=1;i<=n;i++)
scanf("%ld",&v[i]);
sort(v+1,v+n+1,comp);
for(long i=0;i<=NMax+NMax;i++) {
vmin[i]=bsearchMin(1,n,v,i);
vmax[i]=bsearchMax(1,n,v,i);
}
v[1]=v[1];
for(long i=1;i<n;i++)
for(long j=i+1;j<=n;j++) {
minn=vmax[v[j]];
maxx=vmin[v[j]+v[i]];
if(v[j]<minn)
minn++;
rez+=maxx-minn>0 ? maxx-minn : 0;
}
printf("%ld\n",rez);
return 0;
}