Cod sursa(job #1536271)

Utilizator RaileanuCristian Raileanu Raileanu Data 25 noiembrie 2015 21:48:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream f2("nrtri.out");

#define NMAX 820

int a[NMAX];

int main()
{
    int n, i, j;

    f >> n;

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

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

    int n_total= 0;

    for (i=1; i<n; i++)
        for (j= i+1; j<=n; j++)
        {
            int val= a[i]+a[j];
            int nr= upper_bound(a+1, a+n+1, val ) - a;

            if (a[nr] > val || nr > n)
                nr--;

            nr-= j;

            n_total+= nr;
        }

    f2 << n_total;

    f2.close();
    return 0;
}