Cod sursa(job #844956)

Utilizator vendettaSalajan Razvan vendetta Data 30 decembrie 2012 00:32:02
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, a[803];

inline bool check(int x, int y ,int z){
    if (a[x] + a[y] >= a[z] && a[x] + a[z] >= a[y] && a[y] + a[z] >= a[x]) return 1;
    return 0;
}

int cb(int X, int st, int dr){
    while(dr- st > 1){
        int mij = (st + dr) >> 1;
        if ( X >= a[mij] ){
            st = mij;
        }else dr = mij;
    }
    return st;
}

int main(){
    f >> n;
    for(int i=1; i<=n; ++i) f >> a[i];
    sort( a+1, a+n+1 );

    int rez = 0;
    for(int i=1; i<n; ++i){
        for(int j=i+1; j<=n; ++j){// caut cel mai mare element din j+1, n care sa fie >= a[i] + a[j];
            if (a[i] + a[j] >= a[j+1] && j+1<=n){
                int poz = cb(a[i]+a[j], j, n+1);
                //cout << i << " " << j << " " << poz << "\n";
                rez += poz - (j+1)+1;
            }
        }
    }
    //cout << rez << "\n";
    g << rez << "\n";
}