Cod sursa(job #2098668)

Utilizator AndreiTurcasTurcas Andrei AndreiTurcas Data 3 ianuarie 2018 13:13:44
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

int n, v[805], nr = 0;

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-1; ++i)
        for(int j = i+1; j < n; ++j)
    {
        int st = j+1, dr = n;
        while(st <= dr)
        {
            int mid = (st+dr)/2;
            if(v[i] + v[j] >= v[mid])
                st = mid + 1;
            else dr = mid-1;
        }
        nr += (dr-j);
    }
    g << nr;
}