Cod sursa(job #2072013)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 21 noiembrie 2017 12:09:23
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("nrtri.in");
ofstream fo("nrtri.out");

long long nr[60001], v[800];

int main()
{
    long long i, n, j, rez;
    fi >> n;
    for(i = 0; i < n; i++){
        fi >> v[i];
        nr[v[i]]++;
    }
    for(i = 1; i <= 60000; i++)
        nr[i] += nr[i-1];
    sort(v, v+n);
    rez = 0;
    for(i = 0; i < n; i++)
        for(j = i + 1; j < n; j++){
            rez = rez + 1LL * (nr[v[i] + v[j]] - nr[v[j] - v[i] - 1]) - 1;
            if(2 * v[i] >= v[j])
                rez--;
        }
    fo << rez / 3;
    return 0;
}