Cod sursa(job #1207647)

Utilizator mihaimusatMihai Musat mihaimusat Data 13 iulie 2014 15:34:03
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include<algorithm>

using namespace std;

int n, i, j, s, st, dr, mid, sol;
int v[805];

int main()
{
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");

    f >> n;
    for (i=1; i<=n; ++i)
        f >> v[i];
    sort (v+1, v+n+1);
    for (i=1; i<=n-2; ++i)
        for (j=i+1; j<=n-1; ++j) {
            st = 1; dr = n;
            s = v[i] + v[j];
            while (st <= dr) {
                mid = st + dr;
                mid >>= 1;
                if (v[mid] > s)
                    dr = mid - 1;
                else
                    st = mid + 1;
            }
            sol += dr - j;
        }
    g << sol;
    return 0;
}