Cod sursa(job #3279340)

Utilizator 9onelostSendrescu Tudor-Gabriel 9onelost Data 22 februarie 2025 16:19:27
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
#define DIM 1000
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, nrc;

int v[DIM];

int cautare(int st, int dr, int val) {

    int ret = st - 1, mij;

    while (st <= dr) {

        mij = (st + dr) / 2;

        if (v[mij] <= val) {

            ret = mij;

            st = mij + 1;

        }

         else {

            dr = mij - 1;

        }

    }

    return ret;

}

int main() {

    fin >> n;

    for (int i = 1; i <= n; i++) {

        fin >> v[i];

    }

    sort(v + 1, v + n + 1);

    for (int i = 1; i <= n - 2; i++) {

        for (int j = i + 1; j <= n - 1; j++) {

            int maxval = v[i] + v[j];

            int poz = cautare(j + 1, n, maxval);

            nrc += poz - j;
        }

    }

    fout << nrc;

    return 0;
}