Cod sursa(job #1202909)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 30 iunie 2014 01:25:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <algorithm>
#define DIMN 805

using namespace std;

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

int n, s, st, dr, mid, sol;

int v[DIMN];

int main () {
    f >> n;
    for (int i=1; i<=n; ++i)
        f >> v[i];
    sort (v+1, v+n+1);
    for (int i=1; i<=n-2; ++i)
        for (int 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;
}