Pagini recente » Monitorul de evaluare | Cod sursa (job #3361491)
//incercam fara sortare eficienta, altfel facem cu sort din algorithm
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int main() {
int n, l[800], i, j, nr = 0, s;
fin >> n;
for (i = 0; i < n; ++i)
fin >> l[i];
//sortare cu sort
sort(l, l + n); //de la l[0] la l[n-1], e interv [0, n)
//numarare cu cautare binara pe cel mai mic termen mai mare sau egal cu l[i] - l[j].
for (i = n - 1; i > 1; --i) {
for (j = i - 1; j > 0; --j) {
s = l[i] - l[j];
if (l[j-1] >= s) {
int lt = 0, rt = j - 1, mid;
while (lt <= rt) {
mid = (lt + rt) / 2;
if (l[mid] >= s)
rt = mid - 1;
else if (l[mid] < s)
lt = mid + 1; //lt va da poz celui mai mic nr >= s
}
nr += j - lt;
}
else
break;
}
}
fout << nr;
}