Cod sursa(job #2113194)

Utilizator BaldurCronos Baldur Data 24 ianuarie 2018 12:39:36
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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;

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

        return l - 1;
}

int main() {
        in >> n;
        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 += bin_search(a[i] + a[j], j + 1, n) - j;
        }

        out << sol;
        return 0;
}