Cod sursa(job #1087303)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 19 ianuarie 2014 11:17:47
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, sum, dr, st, mid, cnt;
vector<int> a;

int main()
{
    is >> n;
    a = vector<int>(n);
    for ( int i = 0; i < n; i++ )
        is >> a[i];
    sort( a.begin(), a.end() );
    for ( int i = 0; i <= n - 2; i++ )
        for ( int j = i + 1; j <= n - 1; j++ )
        {
            sum = a[i] + a[j];
            dr = n - 1;
            st = j + 1;
            while ( st < dr )
            {
                mid = (st + dr) / 2;
                if ( a[mid] > sum )
                    dr = mid - 1;
                else
                    st = mid + 1;
            }
            if ( sum >= a[dr] )
                dr++;
            cnt += dr - j - 1;
        }
    os << cnt;
    is.close();
    os.close();
    return 0;
}