Cod sursa(job #1557566)

Utilizator nytr0gennytr0gen nytr0gen Data 27 decembrie 2015 19:47:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int NMAX = 800;

int bin_search(int *v, int n, int k) {
    int step = 1 << 10;
    int pos = 0;
    while (step >>= 1) {
        if (pos + step < n && v[pos + step] <= k) {
            pos += step;
        }
    }

    return pos;
}

int main() {
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    int n; scanf("%d", &n);
    int v[NMAX];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &v[i]);
    }

    sort(v, v + n);

    int sum = 0;
    for (int i = 0; i < n - 2; ++i) {
        for (int j = i + 1; j < n - 1; ++j) {
            sum += bin_search(v + j, n - j, v[i] + v[j]);
        }
    }

    printf("%d\n", sum);

    return 0;
}