Cod sursa(job #2444714)

Utilizator CostiVVoicu Costi CostiV Data 1 august 2019 10:25:12
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>
using namespace std;

int main (){
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");

    int N;
    fin >> N;
    int i, v[805];
    for (i = 1; i <= N; ++i)
        fin >> v[i];
    sort(v + 1, v + N + 1);
    int nr = 0;
    for (i = 1; i <= N-2; ++i)
        for (int j = i + 1; j <= N-1; ++j){
            int l = 1, r = N, m;
            int s = v[i] + v[j], c = 0;
            while (l <= r){
                m = (l + r) / 2;
                if (v[m] <= s){
                    l = m + 1;
                }
                else{
                    r = m - 1;
                }
            }
            nr += (r - j);
        }
    fout << nr;
    return 0;
}