Pagini recente » Borderou de evaluare (job #1879244) | Cod sursa (job #3122262) | Cod sursa (job #1171088) | Cod sursa (job #2727810) | Cod sursa (job #364270)
Cod sursa(job #364270)
#include<fstream>
using namespace std;
int v[801],n;
int partition(int p,int r)
{int x=v[r];
int i=p-1;
for(int j=p;j<r;j++) {if(v[j]<x) {i++;int aux=v[j];v[j]=v[i];v[i]=aux;}}
int aux2=v[r];v[r]=v[i+1];v[i+1]=aux2;
return i+1;
}
void quicksort(int p,int q)
{if(p<q)
{int m=partition(p,q);
quicksort(p,m-1);
quicksort(m+1,q);
}
}
int cautare(int p, int u,int i,int j)
{
int m;
m=(p+u)/2;
while (p<=u){
if ((v[m]<=v[i]+v[j] && v[m+1]>v[i]+v[j]) || (v[m]<=v[i]+v[j] && m==n-1))
return m;
else if (v[m]<=v[i]+v[j] && v[m+1]<=v[i]+v[j]) {
p=m+1;
m=(p+u)/2;
}
else {
u=m-1;
m=(p+u)/2;
}
}
return 0;
}
int main()
{freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
int rez=0;
for(int i=0;i<n;i++) scanf("%d",&v[i]);
quicksort(0,n-1);
for(int i=0;i<=n-1;i++)
for(int j=i+1;j<=n-2;j++)
{int r=cautare(0,n,i,j);
if(r>=j && r!=0) rez+=r-j;
}
printf("%d",rez);
return 0;
}