Cod sursa(job #1562656)

Utilizator sherban26FMI Mateescu Serban-Corneliu sherban26 Data 5 ianuarie 2016 13:06:33
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define NMAX 810

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

vector<int> v;
int n;

int main()
{
    fin >> n;
    int x;
    for (int i = 0; i < n; ++i)
    {
        fin >> x;
        v.push_back(x);
    }

    sort(v.begin(), v.end());
    int rez = 0;
    //mi-e lene
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
        {
            int k = upper_bound(v.begin(), v.end(), v[i] + v[j]) - v.begin() - 1;
            if (k >= n) continue;
            rez += max(0, k - j);
        }

    fout << rez;

    return 0;
}