Cod sursa(job #1674673)

Utilizator andysolNelIdiot andysol Data 4 aprilie 2016 19:56:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
using namespace std;

#include <cstdio>
#include <cassert>
#include <algorithm>

#define FIN "nrtri.in"
#define FOUT "nrtri.out"
#define NMAX 801

int N, a[NMAX];

int binsearch(int i, int j)
{
    int t, step, val = a[i] + a[j];
    
    for (step = 1; step <= N; step <<= 1);
    for (t = j; step; step >>= 1)
        if (t + step <= N && a[t + step] <= val)
            t += step;
    return t - j;
}

int
main ()
{
    int ct = 0;
    
    freopen ("nrtri.in", "rt", stdin);
    freopen ("nrtri.out", "wt", stdout);
    
    scanf ("%d",&N);
    for (int i = 1; i <= N; ++ i)
        scanf ("%d",&a[i]);
    sort (a+1,a+N+1);
    for (int i = 1; i <= N-1; ++ i)
        for (int j = i + 1; j <= N; ++ j)
            ct += binsearch(i, j);
    
    printf ("%d\n",ct);
    return 0;
}