Pagini recente » Cod sursa (job #1543974) | Cod sursa (job #2991100) | Cod sursa (job #2133095) | Cod sursa (job #2226120) | Cod sursa (job #526156)
Cod sursa(job #526156)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
freopen ("nrtri.in", "r", stdin);
freopen ("nrtri.out", "w", stdout);
int N;
vector <int> B;
scanf ("%d", &N);
for (int i = 0; i < N; ++i)
{
int numar;
scanf ("%d", &numar);
B.push_back(numar);
}
sort (B.begin(), B.end());
//N^2logN
int rezultat = 0;
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
{
int st = j + 1, dr = N - 1, lim = B[i] + B[j];
while (st < dr - 1)
{
int mij = (st + dr)/2;
if (B[mij] <= lim) st = mij;
else dr = mij - 1;
}
int ul;
if (B[dr] <= lim) ul = dr;
else if (B[st] <= lim) ul = st;
else ul = st - 1;
rezultat += (ul - j);
}
printf ("%d", rezultat);
return 0;
}