Cod sursa(job #2602360)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 16 aprilie 2020 19:22:45
Problema Numarare triunghiuri Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 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];
            solutie += mai_mic[limita_sus] - mai_mic[limita_jos];
        }
    }
    fout << solutie;
    return 0;
}