Pagini recente » Cod sursa (job #2772730) | Cod sursa (job #917959) | Cod sursa (job #704138) | Clasamentul arhivei Infoarena Monthly | Cod sursa (job #588185)
Cod sursa(job #588185)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define Fin "nrtri.in"
#define Fout "nrtri.out"
using namespace std;
int n,i,j,u,x,nr,st,dr,mij;
vector <int> v;
int main()
{
freopen(Fin,"r",stdin);
freopen(Fout,"w",stdout);
scanf("%d",&n);
v.push_back(0);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
v.push_back(x);
}
sort(v.begin()+1,v.end());
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
u=v[i]+v[j];
if(u>=v[n])
nr+=(n-j);
else
{
st=j+1;
dr=n;
while(st<dr)
{
mij=(st+dr)/2;
if(v[mij]<u)st=mij+1;
else dr=mij-1;
}
nr+=(dr-j-1);
}
}
printf("%d",nr);
}