Pagini recente » Cod sursa (job #3338858) | Statistici Sebastian Butnariuc (sebastianandrei1234) | Cod sursa (job #3338890) | Rating dekeeu deke (dekeeu) | Cod sursa (job #3324459)
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int main() {
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n;
int v[801];
in >> n;
for (int i = 0; i < n; i++) {
in >> v[i];
}
sort(v, v + n);
long long total = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int suma = v[i] + v[j];
/// Cautam binar prima pozitie unde v[k] >= suma
int st = j + 1, dr = n - 1;
int pos = n; /// prima pozitie invalida
while (st <= dr) {
int mid = st + (dr - st) / 2;
if (v[mid] >= suma) {
pos = mid;
dr = mid - 1;
} else {
st = mid + 1;
}
}
///toate betisoarele de la j + 1 la pos - 1 pot forma triunghi cu perechea
total += (pos - j - 1);
}
}
out << total << endl;
return 0;
}