Cod sursa(job #1723686)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 1 iulie 2016 13:12:08
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

ofstream g("nrtri.out");

int n, a[850], cnt;

void Citire()
{
    ifstream f("nrtri.in");
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> a[i];
    f.close();
}

void CB(int x, int y)
{
    int sum, m, st, dr, poz;
    sum = a[x] + a[y];
    st = y + 1;
    dr = n;
    poz = -1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(sum >= a[m])
        {
            poz = m;
            dr = m - 1;
        }
        else st = m + 1;
    }
    if(poz != -1)
        cnt += poz - y;
}

void Rezolvare()
{
    int i, j;
    sort(a + 1, a + n + 1);
    for(i = 1; i < n - 1; i++)
        for(j = i + 1; j < n; j++)
            CB(i, j);
    g << cnt << "\n";
    g.close();
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}