Cod sursa(job #2073848)

Utilizator edi9876Negescu Eduard Mihai edi9876 Data 23 noiembrie 2017 19:30:16
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

const int NL = 801, L = 16;
int n, v[NL];

int fct(int i, int j)
{
    int r = 0;
    int pas = 1 << L;
    while(pas != 0)
    {
        if(r + pas <= n && v[r + pas]<= v[i] + v[j])
        {
            r += pas;
        }
        pas /= 2;
    }
    return r;
}

int main()
{
    in >> n;
    int c = 0;
    for(int i = 1; i <= n; i++)
    {
        in >> v[i];
    }
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            c += fct(i, j) - j;
        }
    }
    out << c << '\n';
    return 0;
}