Cod sursa(job #1535840)

Utilizator lauratenderLaura Tender lauratender Data 25 noiembrie 2015 11:30:30
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("nrtri.in");
ofstream out ("nrtri.out");
int v[801];
int main()
{
    int i, n, x,pas, j, y, rez=0;
    in>>n;
    for (i=1; i<=n; i++)
    {
        in>> x;
        v[i] = x;

    }
    sort ( v+1, v+n+1);
    for (i = 1; i <= n - 2; i++)
        for (j = i + 1; j <= n - 1; j++)
        {
            //caut binar cel mai mare k cu proprietatea v[k] <= v[i] + v[j]
            pas=1<<15;
            x=0;
            while ( pas != 0)
            {
                if ( x + pas <= n && v[x+pas]<= v[i] + v[j])
                    x += pas;
                pas/=2;
            }
            rez = rez +  x - j;
        }


    out<<rez;

    return 0;
}