Cod sursa(job #3360504)

Utilizator cristiz123456Zoescu Cristian cristiz123456 Data 14 iulie 2026 14:26:59
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>

using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
const int N = 800;
const int VAL_MAX = 30000;
int f[VAL_MAX + 1], v[N];
int main()
{
    int i, n, ap = 1, x, st, dr, mij, j, cnt = 0;
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> x;
        f[x]++;
    }
    for(i = 0; i <= VAL_MAX; i++)
    {
        while(f[i] > 0)
        {
            v[ap++] = i;
            f[i]--;
        }
    }
    for(i = 1; i <= n - 2; i++)
    {
        for(j = i + 1; j <= n - 1; j++)
        {
            x = v[i] + v[j];
            st = j + 2;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(v[mij] <= x)
                {
                    st = mij + 1;
                }
                else
                {
                    dr = mij - 1;
                }
            }
            if(v[st - 1] <= x)
            {
                cnt += st - j - 1;
                //printf("%d %d %d %d\n", v[i], v[j], v[st - 1], st - 1);
            }
        }
    }
    cout << cnt;
    return 0;
}