Cod sursa(job #3324387)

Utilizator iustin251007iustin balint iustin251007 Data 22 noiembrie 2025 10:26:51
Problema Numarare triunghiuri Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>
using namespace std;

int a[801];

int main() {
    ifstream cin("nrtri.in");
    ofstream cout("nrtri.out");

    int N;
    cin >> N;
    for (int i = 0; i < N; i++) 
    cin >> a[i];

    sort(a, a + N);

    long long cnt = 0;

    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            int st = j + 1, dr = N - 1, ans = j;

            while (st <= dr) {
                int mid = st + (dr - st) / 2;
                if (a[i] + a[j] > a[mid]) {
                    ans = mid;
                    st = mid + 1;
                } else {
                    dr = mid - 1;
                }
            }

            cnt += ans - j;
        }
    }

    cout << cnt;

    return 0;
}