Cod sursa(job #2018921)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 6 septembrie 2017 13:11:48
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,i,j,a[805], x;
long long sol;

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

    sort(a+1, a+n+1);

    for (i = 1; i <= n; i++) {
        for (j = 1; j < i; j++) {
            x = a[i]+a[j];
            int st = 1, dr = n, mij;
            if (x >= a[n]) st = n, dr = 1;
            while (st <= dr) {
                mij = (st+dr)/2;
                if (a[mij] > x)
                    dr = mij-1;
                else st = mij+1;
            }
            if (a[st] > x) st--;
            sol += n-st;
            //g << x << ' ' << a[j] << ' ' << a[i] << ' ' << a[st] << '\n';
        }
    }
    g << sol;
}