Cod sursa(job #1870973)

Utilizator savigunFeleaga Dragos-George savigun Data 7 februarie 2017 00:18:03
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const int L = 1 << 10;
int cautare_binara(int v[], int n, int nr) {
    int pas = L;
    int p = 0;

    while (pas != 0) {
        if (p + pas <= n && v[p + pas] <= nr) {
            p += pas;
        }
        pas /= 2;
    }

    return p;
}

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

    int v[801], n, sol = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }

    sort(v + 1, v + n + 1);


    for (int i = 1; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int sum = v[i] + v[j];
            int p1 = cautare_binara(v, n, sum);
            int p2 = cautare_binara(v, n, v[j]) + 1;
            if (p1 >= p2)
                sol += p1 - p2 + 1;
        }
    }

    cout << sol;


    return 0;
}