Cod sursa(job #2911047)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 26 iunie 2022 15:34:11
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda 3_iulie Marime 0.69 kb
#include <fstream>
#include <algorithm>

#define DIM 801

using namespace std;

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

int n, sol;
int v[DIM];

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 - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int x = v[i] + v[j];
            int st = j + 1, dr = n;
            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (v[mid] <= x)
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            sol += (dr - j);
        }
    }

    fout << sol;

    return 0;
}