Cod sursa(job #3274284)

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

int main() {
	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 = 1, dr = n, mij;
            while( st < dr )
            {
                mij = (st+dr)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij] > v[i]+v[j] )
                    dr = mij;
                else
                    st = mij+1;
            }
            //cout << "Avem " << st << "\n";
            int rasaux = n - st+1;
            if( i >= st )
                --rasaux;
            if( j >= st )
                --rasaux;
            if( v[st] <= v[i]+v[j] )
                rasaux = 0;
            ras += rasaux;
        }
    }
    g << ras;
}