Cod sursa(job #3141269)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 iulie 2023 13:49:08
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector <int> v;
int cb(int val, int st, int dr)
{
    int mij=0;
    while (st<dr) {
        mij=(st+dr)/2;
        if (v[mij]<val) st=mij+1;
        else dr=mij;
    }
    return st;
}
int main()
{
    int x;
    cin.tie(0);
    cin.sync_with_stdio(false);
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    int cnt=0;
    for (int i=0; i<n-2; i++)  {
        for (int j=i+1; j<n-1; j++) {
            int suma=v[i]+v[j];
            auto it=lower_bound(v.begin(), v.end(), suma);
            int index=it-v.begin();
            if (v[i]+v[j]<v[index]) continue;
            cnt+=(n-index+1);
        }
    }
    cout<<cnt;
    return 0;
}