Cod sursa(job #3363797)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 23 august 2026 02:16:28
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 800;
int v[MAXN];
int main()
{
    FILE *fin, *fout;
    int i, j, n, rez, k;
    fin = fopen("nrtri.in", "r");
    fscanf(fin, "%d", &n);
    for (i = 0; i < n; i++) {
        fscanf(fin, "%d", &v[i]);
    }
    fclose(fin);
    sort(v, v + n);
    //o(n^2) cu 2 pointers, calculez numarul de triunghiuri care nu sunt valide
    rez = n * (n - 1) * (n - 2) / 6;
    for (i = 0; i < n; i++) {
        j = i + 1;
        k = j + 1;
        while (j < n && k < n) {
            while (k < n && v[i] + v[j] >= v[k]) {
                k++;
            }
            rez -= (n - k);
            j++;
        }
    }
    fout = fopen("nrtri.out", "w");
    fprintf(fout, "%d\n", rez);
    fclose(fout);
    return 0;
}