Cod sursa(job #1930862)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 19 martie 2017 11:50:31
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;


int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    int n;

    scanf("%d", &n);

    vector<int> v(n);
    for (int i = 0; i < n; i ++)
    {
        scanf("%d", &v[i]);
    }

    sort(v.begin(), v.end());

    int counter = 0;

    for (int i = 0; i < n; i ++)
    {
        for (int j = i + 1; j < n; j ++)
        {
            if (j + 1 < n && v[j + 1] <= v[i] + v[j])
            {
                int x = upper_bound(v.begin() + j, v.end(), v[i] + v[j]) - (v.begin() + j + 1);
                counter += x;
            }
        }
    }

    printf("%d\n", counter);
    return 0;
}