Cod sursa(job #2579624)

Utilizator sipdavSipos David Oliver sipdav Data 12 martie 2020 17:58:00
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

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

const int dim = 810;

int n, v[dim], rez, p;

int cauta(int x, int j)
{
    int st = 1, poz = j + 1;
    for(st;st <= n;st <<= 1);
    for(st; st; st >>= 1)
        if(poz + st <= n && v[poz + st] <= x)
            poz += st;
    return poz;
}

int main()
{
    in>>n;
    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++)
        {
            p = cauta(v[i] + v[j], j);
            if(v[p] < v[i] + v[j])
                rez += n - p + 1;
        }
    }
    out<<rez<<'\n';
    return 0;
}