Pagini recente » Cod sursa (job #1326175) | Cod sursa (job #2476946) | Cod sursa (job #326070) | Cod sursa (job #361517) | Cod sursa (job #1546845)
#include <cstdio>
#include <algorithm>
using namespace std;
#define DIM 805
int N, V[DIM];
int bin_search(int in, int sf, int x);
int main() {
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d\n", &N);
for(int i = 1; i <= N; ++i) {
scanf("%d", &V[i]);
}
int answer = 0;
sort(V + 1, V + 1 + N);
for(int i = 1; i < N; ++i) {
for(int j = i + 1; j <= N; ++j) {
int pos = bin_search(j + 1, N, V[i] + V[j]);
if(pos > j) {
answer += pos - j;
}
}
}
printf("%d\n", answer);
return 0;
}
int bin_search(int in, int sf, int x) {
int lg = sf - in + 1;
int p = 1;
while(p <= lg) {
p <<= 1;
}
p >>= 1;
int pos = in - 1;
while(p) {
if(pos + p <= sf) {
if(V[pos + p] <= x) {
pos += p;
}
}
p >>= 1;
}
return pos;
}