Pagini recente » Cod sursa (job #1119434) | Cod sursa (job #250227) | Cod sursa (job #385826) | Cod sursa (job #2216037) | Cod sursa (job #1701611)
#include <bits/stdc++.h>
using namespace std;
int n,a[810];
void Citire()
{
freopen("nrtri.in","r",stdin);
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
}
void Aux(int &x,int &y)
{
int aux;
aux=x;
x=y;
y=aux;
}
int Partitionare(int st,int dr)
{
int p,piv,i,j;
p=rand()%(dr-st+1)+st;
Aux(a[p],a[st]);
piv=a[st];
i=st+1;
j=dr;
while(i<=j)
{
if(a[i]<=piv) i++;
if(a[j]>piv) j--;
if((i<j) && (a[i]>piv) && (a[j]<=piv))
{
Aux(a[i],a[j]);
i++;
j--;
}
}
a[st]=a[i-1];
a[i-1]=piv;
return i-1;
}
void QS(int st,int dr)
{
int p;
p=Partitionare(st,dr);
if(st<p-1) QS(st,p-1);
if(p+1<dr) QS(p+1,dr);
}
int Sol()
{
int i,j,k=0,nrtri=0;
for(i=1;i<=n;i++)
{
k=i+2;
for(j=i+1;j<=n;j++)
{
while(k<=n && a[i]+a[j]>=a[k]) k++;
if(j+1<=k+1) nrtri+=k-j-1;
}
}
return nrtri;
}
int main()
{
Citire();
QS(1,n);
freopen("nrtri.out","w",stdout);
printf("%d\n",Sol());
return 0;
}