Cod sursa(job #3274290)

Utilizator SimifilLavrente Simion Simifil Data 6 februarie 2025 00:48:42
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");

int main() {
    ios_base::sync_with_stdio(false);
    f.tie(NULL);
	int n;
    f >> n;
    int v[n+1];
    long long ras = 0;
    for( int i = 1; i <= n; ++i )
    {
        f >> v[i];
    }
    sort( v+1, v+1+n );
    for( int j = 2; j < n; ++j )
    {
        for( int i = 1; i < j; ++i )
        {
            //cout << "Analizam " << v[i] << " " << v[j] << ", " << i << " " << j << "\n";
            ///v[i] + v[j] > v[x]
            int st = j+1, dr = n, mij;
            while( st < dr )
            {
                mij = (st+dr)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij+1] < v[i]+v[j] )
                    st = mij+1;
                else
                    dr = mij;
            }
            //cout << "Avem " << st << "\n";
            int rasaux = st-(j+1)+1;
            if( v[st] >= v[i]+v[j] )
                rasaux = 0;
            ras += rasaux;
        }
    }
    g << ras;
    return 0;
}