Pagini recente » Cod sursa (job #2696524) | Cod sursa (job #2699562) | Cod sursa (job #1164102) | Cod sursa (job #849303) | Cod sursa (job #980531)
Cod sursa(job #980531)
// Theta(n*n*log(n))
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=810;
int n,v[MAXN],sol;
void read()
{
FILE *fin=fopen("nrtri.in","r");
fscanf(fin,"%d",&n);
for (int i=1; i<=n; ++i)
fscanf(fin,"%d",&v[i]);
fclose(fin);
}
int binary_search(int low,int high, int value)
{
int mid;
while (low<=high)
{
mid=(low+high)/2;
if (v[mid]<=value)
{
int aux=mid+1;
while (v[aux]<=value && aux<=n)
++aux;
return aux-1;
}
else if (v[mid]>value)
high=mid-1;
}
return 0;
}
void solve()
{
int i,j,k=0;
for (i=1; i<=n-2; ++i)
{
for (j=i+1; j<=n-1; ++j)
{
k=binary_search(j+1,n,v[i]+v[j]);
if (k)
{
sol+=(k-j);
}
}
}
}
void write()
{
FILE *fout=fopen("nrtri.out","w");
fprintf(fout,"%d\n",sol);
fclose(fout);
}
int main()
{
read();
sort(v+1,v+n+1);
solve();
write();
return 0;
}