Cod sursa(job #2205531)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 19 mai 2018 14:20:37
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 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 = i + 1; j <= n; ++ j){
            int lgMax = v[j] + v[i];
            lgMax = min(MAX - 1, lgMax);
            int st = j + 1, dr = n;
            while(st <= dr){
                int mid = (st + dr) / 2;
                if(v[mid] <= lgMax)
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            sol += dr - j;
        }
    }
    
    out<<sol;
    
    return 0;
}