Cod sursa(job #2075144)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 25 noiembrie 2017 11:30:52
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[805];
int lg=1;
int s=0;
void cit()
{
    scanf("%d\n", &n);
    for(int i=1; i<=n; i++)
        scanf("%d ", &a[i]);
    sort(a+1, a+n+1);
}

int cautbin(int l, int s, int j)
{
    int i;
    for(i=j; l > 0; l>>=1)
        if(i+l <=n && a[i+l] <= s)
            i+=l;
    return i;

}


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

    for(lg=1; lg <= n; lg<<=1);

    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<=n; j++)
            {
                int poz=cautbin(lg, a[i]+a[j], j);
                s=s+(poz-j);
            }
    }
    printf("%d", s);

    return 0;
}