Cod sursa(job #2205528)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 19 mai 2018 14:13:07
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#define DIM 1002
#define MAX 30002

using namespace std;

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

int n, v[DIM], viz[MAX], sol;

int main(int argc, const char * argv[]) {
    in>>n;
    for(int i = 1; i <= n; ++ i){
        in>>v[i];
        ++ viz[v[i]];
    }
    
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= 30001; ++ i)
        viz[i] += viz[i - 1];
    
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            if(i == j)
                continue;
            int lgMin = abs(v[j] - v[i]);
            int lgMax = v[j] + v[i];
            lgMax = min(MAX - 1, lgMax);
            lgMin = min(MAX - 1, lgMin);
            sol += viz[lgMax] - viz[lgMin - 1];
            if(lgMin <= v[i] && v[i] <= lgMax)
                -- sol;
            if(lgMin <= v[j] && v[j] <= lgMax)
                -- sol;
        }
    }
    
    out<<sol / 3;
    
    return 0;
}