Pagini recente » Cod sursa (job #2256230) | Cod sursa (job #288013) | Cod sursa (job #2566333) | Cod sursa (job #1105273) | Cod sursa (job #17492)
Cod sursa(job #17492)
#include <stdio.h>
#define NMAX 1000
int n;
long a[NMAX];
long long count;
void read()
{
int i;
scanf("%d\n", &n);
for(i = 0; i < n; ++i)
scanf("%ld ", &a[i]);
}
int divide(int p, int q)
{
int st = p, dr = q;
long x = a[p];
while(st < dr)
{
while(st < dr && x <= a[dr]) --dr;
a[st] = a[dr];
while(st < dr && x >= a[st]) ++st;
a[dr] = a[st];
}
a[st] = x;
return st;
}
void qsort(int p, int q)
{
int m = divide(p, q);
if(m-1 > p)
qsort(p, m-1);
if(m+1 < q)
qsort(m+1, q);
}
void solve()
{
int for1, for2;
int st, dr, m;
long suma;
for(for1 = 0; for1 < n; ++for1)
for(for2 = for1+1; for2 < n; ++for2)
{
st = for2;
dr = n-1;
suma = a[for1] + a[for2];
while(st <= dr)
{
m = (st+dr)/2;
if(a[m] > suma && a[m-1] <= suma)
{
--m;
break;
}
else if(a[m] <= suma)
{
st = m+1;
}
else
{
dr = m-1;
}
}
count += m-for2;
}
}
int main()
{
freopen("nrtri.in", "r", stdin);
freopen("nrtri.out", "w", stdout);
read();
qsort(0, n-1);
solve();
printf("%lld\n", count);
fclose(stdin);
fclose(stdout);
return 0;
}