Cod sursa(job #1360266)

Utilizator retrogradLucian Bicsi retrograd Data 25 februarie 2015 13:23:38
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;
typedef int var;

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

#define MAXN 801

var L[MAXN];

var bs(var b, var e, var val) {
    var *p = L+b-1;
    e -= b-1;
    var i, poz=0;
    for(i=1; i<=e; i<<=1);
    for(i>>=1;i;i>>=1) {
        if(poz+i<=e && p[poz+i] <= val) {
            poz += i;
        }
    }
    return poz;
}

int main() {
    var n;
    fin>>n;
    for(var i=1; i<=n; i++) {
        fin>>L[i];
    }
    sort(L+1, L+n+1);

    var poz, total = 0;

    for(var i=1; i<n-1; i++) {
        for(var j=i+1; j<n; j++) {
            var poz = bs(j+1, n, L[i] + L[j]);
            total += poz;
        }
    }

    fout<<total;

    return 0;
}