Cod sursa(job #961569)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 12 iunie 2013 16:55:52
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb

#include <fstream>
#include <algorithm>
using namespace std;

long N;
long C[900];

long Cnt[70000];

long Res;

int main(void)
{
    fstream fin("nrtri.in",ios::in);
    fstream fout("nrtri.out",ios::out);

    fin >> N;
    for (long a = 0;a < N;a += 1)
    {
        fin >> C[a];
    }

    sort(C + 0,C + N);

    for (long a = 0;a < N;a += 1)
    {
        for (long b = (a + 1);b < N;b += 1)
        {
            long x = upper_bound(C + 0,C + N,C[b] + C[a]) - C;
            long y = lower_bound(C + 0,C + N,C[b] - C[a]) - C;
            if (y < (b + 1))
            {
                y = (b + 1);
            }
            long z = x - y;
            if (z > 1)
            {
                z -= 2;
            }
            Res += z;
        }
    }

    fout << Res;

    fin.close();
    fout.close();
    return 0;
}