Cod sursa(job #2311155)

Utilizator aurelionutAurel Popa aurelionut Data 2 ianuarie 2019 18:17:48
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int MAX = 30005;
const int NMAX = 2005;
int n, v[NMAX], frecv[MAX], ans;

int main()
{
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    fin >> n;
    for (int i = 1;i <= n;++i)
    {
        fin >> v[i];
        ++frecv[v[i]];
    }
    for (int i = 1;i < MAX;++i)
        frecv[i] += frecv[i - 1];
    sort(v + 1, v + n + 1);
    for (int i = 1;i < n;++i)
        for (int j = i + 1;j <= n;++j)
        {
            int st = max(0, v[j] - v[i] - 1);
            int dr = min(v[j] + v[i], MAX - 1);
            int aux = frecv[dr] - frecv[st];
            if (st < v[i] && v[i] < dr)
                --aux;
            if (st < v[j] && v[j] < dr)
                --aux;
            ans += aux;
        }
    fout << ans / 3 << "\n";
    fin.close();
    fout.close();
    return 0;
}