Cod sursa(job #2075079)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 25 noiembrie 2017 11:17:40
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[801];
int lg;
int s=0;
void cit()
{
    scanf("%d", &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; lg > 0; lg>>=1)
        if(i+lg <=n && a[i] <= s)
            i+=lg;
    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++)
            s=s+(cautbin(lg, a[i]+a[j], j)-j);
    printf("%d", s);

    return 0;
}