Cod sursa(job #2931366)

Utilizator Luka77Anastase Luca George Luka77 Data 30 octombrie 2022 23:30:09
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 805;
int n, arr[NMAX], ans;

inline int b_search(int st, int dr, int val)
{
    int cnt = 0;
    while(st <= dr)
    {
        int mid = (st + mid) / 2;
        if(val >= arr[mid])
            st++, cnt++;
        else
            dr = mid-1;
    }
    return cnt;
}

inline void solve()
{
    sort(arr+1, arr+n+1);
    for(int i=1;i<n;++i)
    {
        for(int j=i+1;j<=n;++j)
        {
            int l = b_search(j+1, n, arr[i]+arr[j]);
            ans+=l;
        }
    }
    fout << ans;
}

int main()
{
    fin >> n;
    for(int i=1;i<=n;++i)
        fin >> arr[i];
    solve();
}