Cod sursa(job #2602359)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 16 aprilie 2020 19:19:41
Problema Numarare triunghiuri Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <algorithm>
#define nmax 30005
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int mai_mare[nmax];
int mai_mic[nmax];
int nr_bete[nmax];
int bat[805];

int main()
{
    int numar_bete;
    fin >> numar_bete;
    for(int i = 1; i <= numar_bete; i++)
    {
        fin >> bat[i];
        nr_bete[bat[i]]++;
    }
    sort(bat + 1, bat + numar_bete + 1);
    for(int i = 1; i <= 30000; i++)
    {
        mai_mic[i] += mai_mic[i - 1] + nr_bete[i];
    }
    int solutie = 0;
    for(int i = 1; i <= numar_bete; i++)
    {
        for(int j = i + 1; j <= numar_bete; j++)
        {
            int limita_sus = bat[j] + bat[i];
            int limita_jos = bat[j] - bat[i] - 1;
            if(bat[i] > limita_jos && bat[i] <= limita_sus )
                solutie--;
            if(bat[j] > limita_jos && bat[j] <= limita_sus )
                solutie--;
            solutie += mai_mic[limita_sus] - mai_mic[limita_jos];
        }
    }
    fout << solutie / 3;
    return 0;
}