Pagini recente » Cod sursa (job #961982) | Cod sursa (job #1842890) | Prezentare infoarena | Cod sursa (job #2494590) | Cod sursa (job #1557057)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n, v[805],nr;
int Divide(int p, int q)
{ int st=p,dr=q,x=v[p];
while(st<dr)
{
while(st<dr && v[dr]>=x)
dr--;
v[st]=v[dr];
while(st<dr && v[st]<=x)
st++;
v[dr]=v[st];}
v[st]=x;
return st;
}
void qsort(int p, int q)
{ int m=Divide(p,q);
if(p<m)
qsort(p,m-1);
if(m<q)
qsort(m+1,q);
}
int cauta(int dr, int stg, int s)
{
int poz=stg;
while(stg<=dr)
{
int mij=(stg+dr)/2;
if(v[mij]<=s)
{
poz=max(mij,poz);
stg=mij+1;
}
else
dr=mij-1;
}
return poz;
}
int main()
{
int i,j,ss;
in>>n;
for(i=1;i<=n;i++)
in>>v[i];
qsort(1,n);
for(i=1;i<=n-2;i++)
for(j=i+1;j<=n-1;j++)
{
ss=v[i]+v[j];
if(v[j+1]<ss)
nr+=cauta(j+1,n,ss)-j;
}
out<<nr;
in.close();
out.close();
return 0;
}