Cod sursa(job #3371229)

Utilizator MMticaCibu Aida MMtica 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;
}