Pagini recente » Cod sursa (job #2134057) | Cod sursa (job #1517652) | Cod sursa (job #122846) | Cod sursa (job #1237314) | Cod sursa (job #903549)
Cod sursa(job #903549)
#include <cstdio>
#include <algorithm>
#define NMax 30001
using namespace std;
long n,vmin[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(val<v[mid])
fn=mid-1;
else
in=mid;
}
return mid;
}
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);
}
for(long i=1;i<n;i++)
for(long j=i+1;j<=n;j++) {
maxx=vmin[v[j]+v[i]];
rez+=maxx-j > 0 ? maxx-j : 0;
}
printf("%ld\n",rez);
return 0;
}