Cod sursa(job #2113207)

Utilizator BaldurCronos Baldur Data 24 ianuarie 2018 12:48:25
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define N 802
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
long long sol;
int n, a[N];

int bin_search(int x, int l, int r) {
        int m, pos = 0;

        while (l <= r) {
                m = (l + r) >> 1;
                if (x >= a[m]) {
                      pos = m;
                      l = m + 1;
                } else {
                        r = m - 1;
                }
        }

        return pos;
}

int main() {
        in >> n;
        if (n < 3) {
                out << 0;
                return 0;
        }

        for (int i = 1; i <= n; i++)
                in >> a[i];

        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n - 2; i++) {
                for (int j = i + 1; j <= n - 1; j++)
                        sol += max(0, bin_search(a[i] + a[j], j + 1, n) - j);
        }

        out << sol;
        return 0;
}