Cod sursa(job #2285603)

Utilizator CristyXtremeSimion Cristian CristyXtreme Data 18 noiembrie 2018 19:53:05
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

inline int caut(int *v, int n, int x) {
    int pos, i;
    for (pos = 1; pos < n; pos <<= 1);
    for (i = 0; pos; pos >>= 1)
        if (i + pos <= n - 1 && v[i + pos] <= x)
            i += pos;
    return i;
}

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    int n, l[30000], sol = 0;
    scanf("%i", &n);
    for (int i = 0; i < n; i++)
        scanf("%i", &l[i]);
    sort(l, l + n);
    for (int i = 0; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            if (l[i] + l[j] > l[n - 1])
                sol += n - 1 - j;
            else
                sol += caut(l, n, l[i] + l[j]) - j;
    printf("%i", sol);
    return 0;
}