Cod sursa(job #3371229)
| Utilizator | Data | 29 octombrie 2026 12:41:20 | |
|---|---|---|---|
| Problema | Numarare triunghiuri | Scor | 70 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 1.5 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int main() {
int n, v[800], cnt = 0, ap[30000] = {0};
fin >> n;
for (int i = 0; i < n; i++) {
int x;
fin >> x;
v[i] = x;
ap[x]++;
}
sort(v, v + n);
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int start = v[j] - v[i];
int final = v[i] + v[j];
if (start < v[j]) {
start = v[j];
}
if (final > v[n - 1]) {
final = v[n - 1];
}
for (int k = start; k <= final; k++) {
int nrap = 0;
if (ap[k]) {
if (k == v[j] && v[j + 1] == k) {
int st = j + 1, dr = n - 1, poz = dr;
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (k < v[mij]) {
dr = mij - 1;
}
else {
poz = mij;
st = mij + 1;
}
}
nrap = poz - j;
}
if (k != v[j]) {
nrap = ap[k];
}
}
cnt += nrap;
}
}
}
fout << cnt;
return 0;
}