Pagini recente » Statistici DenisBadarau (DenisBadarau) | Cod sursa (job #1703645) | Cod sursa (job #2361684) | Cod sursa (job #1441574) | Cod sursa (job #350079)
Cod sursa(job #350079)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define NMAX 5005
#define INF 1000000
vector <int> A;
vector <int> S;
bool MySortPredicate(const int d1, const int d2)
{
return d1 < d2;
}
int bin(int l, int h, int k)
{
int mid = (l+h)/2;
if (l==h)
return l;
if (A[mid] < k)
return bin(mid+1, h, k);
else
return bin(l,mid, k);
}
int main()
{
int i,a,N,j,h,l;
char buf[100];
long sum=0;
freopen("nrtri.in", "rt", stdin);
freopen("nrtri.out", "wt", stdout);
scanf("%d",&N);
for (i=0;i<N;i++)
{
scanf("%d",&a);
A.pb(a);
}
sort(A.begin(),A.end(),MySortPredicate);
A.pb(INF);
/*
for (i=0;i<N;i++)
printf("%d ",A[i]);
printf("\n");
*/
for (i=0;i<N;i++)
for (j=i+1;j<N;j++)
{
h = bin(0,N,A[i]+A[j]);
while (A[i]+A[j] >= A[h])
h++;
sum+= h - j - 1;
//printf("H:%d %d Sum:%ld\n",A[i]+A[j],h,sum);
}
printf("%ld\n",sum);
return 0;
}