Cod sursa(job #2923996)

Utilizator Alex18maiAlex Enache Alex18mai Data 22 septembrie 2022 18:48:30
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

//ifstream cin ("input"); ofstream cout ("output");
ifstream cin ("nrtri.in"); ofstream cout ("nrtri.out");

vector <int> v;

int main() {

    int n;
    cin>>n;

    v.resize(n);
    for (int i=0; i<n; i++){
        cin>>v[i];
    }
    sort(v.begin(), v.end());

    int sum = 0;

    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            //i si j fixate
            //il cautam pe k a.i. v[k] <= v[i] + v[j]
            int st = j+1;
            int dr = n-1;
            int numarElementeBune = 0;

            while (st <= dr){
                int mij = (st + dr) / 2;
                if (v[mij] <= v[i] + v[j]){
                    numarElementeBune = mij - j;
                    st = mij + 1;
                }
                else{
                    dr = mij - 1;
                }
            }

            sum += numarElementeBune;
        }
    }

    cout<<sum<<'\n';

    return 0;
}