Cod sursa(job #2653986)

Utilizator KillHorizon23Orban Robert KillHorizon23 Data 29 septembrie 2020 17:20:57
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[805], n;
int CautBn(int s, int val)
{
        int d = n, m;
        while (s <= d)
        {
                m = (s + d) / 2;
                if (v[m] > val)
                        d = m - 1;
                else s = m + 1;
        }
        return d;
}
int main()
{
        ios::sync_with_stdio(false);
        fin.tie(0);

        fin >> n;
        for (int i = 1; i <= n; ++i)
                fin >> v[i];
        sort(v + 1, v + 1 + n);
        int cnt = 0;
        for (int i = 1; i < n - 1; ++i)
                for (int j = i + 1; j < n; ++j)
                        cnt += CautBn(j + 1, v[i] + v[j]) - j;
        fout << cnt;

        return 0;
}