Cod sursa(job #214763)

Utilizator Mishu91Andrei Misarca Mishu91 Data 15 octombrie 2008 20:48:59
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX_N 805
#define INF 0x3f3f3f3f

int V[MAX_N], S, Rez;
int N;
int logN;

int b_search ()
{
    int i, lg;
    for(i = N + 1, lg = logN; lg; lg >>= 1)
        if(i - lg > 0 && V[i - lg] > S)
            i -= lg;

    return i;

}

void citire()
{
    scanf("%d\n",&N);

    for(int i = 1; i <= N; ++i)
        scanf("%d",V+i);
    V[N+1] = INF;
}

void solve()
{
    for(logN = 1; logN < N + 1; logN <<= 1);
    sort(V+1, V+N+1);

    for(int i = 1; i < N; ++i)
        for(int j = i + 1; j < N; ++j)
        {
            S = V[i] + V[j];

            int nr = b_search();
            Rez += (nr - 1 - j);
        }
    printf("%d\n",Rez);
}

int main()
{
    freopen("nrtri.in","rt",stdin);
    freopen("nrtri.out","wt",stdout);
    citire();
    solve();
}