Cod sursa(job #3141252)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 iulie 2023 13:40:33
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <iostream>
#include <algorithm>
using namespace std;
int v[805], n;
int cb(int val, int st, int dr)
{
    int mij=0;
    while (st<dr) {
        mij=(st+dr+1)/2;
        if (v[mij]<=val) st=mij;
        else dr=mij-1;
    }
    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>>v[i];
    sort(v+1, v+n+1);
    int cnt=0;
    for (int i=1; i<=n-2; i++)  {
        for (int j=i+1; j<=n-1; j++) {
            int suma=v[i]+v[j];
            int fi=cb(suma, j+1, n);
            if (v[i]+v[j]<v[fi]) continue;
            //cout<<v[i]<<" "<<v[j]<<" "<<v[fi]<<endl;
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}