Cod sursa(job #2155158)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 7 martie 2018 17:32:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int>V;

int binsearch(int a, int b, int value)
{
    if(value<V[a])
        return 0;

    int pos=a, st=a, dr=b, mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(V[mid]<=value)
        {
            pos=mid;
            st=mid+1;
        }
        else
        {
            dr=mid-1;
        }
    }
    return pos-a+1;
}

int main()
{
    int t=0;

    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    scanf("%d ", &n);
    for(int i=1; i<=n; i++)
    {
        int val;
        scanf("%d ", &val);
        V.push_back(val);
    }
    sort(V.begin(),V.end());

    for(int i=0; i<n-2; i++)
    {
        for(int j=i+1; j<n-1; j++)
        {
            t=t+binsearch(j+1, n-1, V[i]+V[j]);
        }
    }
    printf("%d\n", t);
    return 0;
}