Pagini recente » Cod sursa (job #685867) | Cod sursa (job #1267201) | Cod sursa (job #2528533) | Cod sursa (job #1618901) | Cod sursa (job #2256251)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
using namespace std;
int n;
vector<int> a;
int find(int l, int h, int x) {
if (l > h) {
return -1;
}
int mid = (l + h) / 2;
if (mid == h) {
if (a[mid] >= x) {
return mid;
}
else {
return -1;
}
}
if (a[mid] >= x && a[mid + 1] < x) {
return mid;
}
if (a[mid] >= x) {
return find(mid + 1, h, x);
}
return find(l, mid - 1, x);
}
int main() {
freopen("nrtri.in", "r", stdin);
freopen("nrtri.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
a.push_back(x);
}
sort(a.begin(), a.end(), greater<int>());
int sol = 0;
for (int i = 0; i < n; ++i) {
int x = a[i];
for (int j = i + 1; j < n; ++j) {
int y = a[j];
int ndx = find(j + 1, n - 1, x - y);
if (ndx != -1) {
sol += ndx - j;
}
}
}
printf("%d", sol);
return 0;
}