Cod sursa(job #2608310)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 30 aprilie 2020 23:23:16
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, i, j, t, x, y, a[805], b[30005];

int main()
{
    f >> n;
    for(i = 0; i < n; i++)
    {
        f >> a[i];
        b[a[i]]++;
    }
    f.close();

    sort(a + 0, a + n);
    b[0] = 0;
    for(i = 1; i <= 30000; i++)
        b[i] += b[i - 1];
    t = 0;
    for(i = 0; i < n - 1; i++)
        if(!i || a[i] != a[i - 1])
        {
            x = 0;
            for(j = i + 1; j < n; j++)
                if((j == i + 1 || a[j] != a[j - 1]) && a[j] > x)
                {
                    y = max(x, a[j] - a[i] - 1);
                    t += b[a[i] + a[j]] - b[y];
                    if(y <= a[i])
                        t--;
                    if(y <= a[j])
                        t--;
                    x = a[i] + a[j];
                }
        }

    g << t / 2 << '\n';
    g.close();

    return 0;
}