Pagini recente » Cod sursa (job #743157) | Cod sursa (job #1838407) | Cod sursa (job #3152366) | Cod sursa (job #357921) | Cod sursa (job #138015)
Cod sursa(job #138015)
//Hash?: O(n^2)
#include <stdio.h>
#include <algorithm>
#define NM 802
using namespace std;
int a[NM];
int h[60003];
long long sol;
int okpos;
int n;
int main()
{
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
int i, j;
scanf("%d", &n);
for (i=1; i<=n; ++i)
scanf("%d", &a[i]);
sort(a+1, a+n+1);
j=0;
for (i=1; i<=a[n-1]+a[n]; ++i)
{
while (j<=n && a[j]<=i) ++j; --j;
h[i]=j;
}
for (i=1; i<n-1; ++i)
for (j=i+1; j<n; ++j)
if (h[a[i]+a[j]]>j) sol+=h[a[i]+a[j]]-j;
printf("%lld", sol);
fclose(stdin);
fclose(stdout);
return 0;
}