Cod sursa(job #1303056)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 27 decembrie 2014 16:12:24
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream is("nrtri.in");
ofstream os("nrtri.out");

int n;
vector<int> a;
int val, k, s, rez;

int main()
{
    is >> n;
    a.resize(n+1);
    for ( int i = 1; i <= n; i++ )
        is >> a[i];
    sort( a.begin() + 1, a.end() );
    for ( val = 1; val <= n; val <<= 1 );

    for ( int i = 1; i <= n - 2; i++ )
        for ( int j = i + 1; j <= n - 1; j++ )
        {
            s = a[i] + a[j];
            k = 0;
            for ( int poz = val; poz; poz >>= 1 )
                if ( poz + k <= n && a[poz + k] <= s )
                    k += poz;
            rez += k - j;
        }
    os << rez;
    is.close();
    os.close();
    return 0;
}