Cod sursa(job #2020026)

Utilizator ialexia_ioanaAlexia Ichim ialexia_ioana Data 9 septembrie 2017 12:03:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

vector<int>v;
vector<int>:: iterator it;
int n;
int BS(int a, int b)
{
    int st, dr, val, s;
    st=b+1;
    dr+n;
    s=v[a]+v[b];
    it=upper_bound(v.begin()+b,v.end(),s);
    return (int)(it-v.begin())-b-1;
}
int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    int i, j, x, cnt=0;
    scanf("%d" ,&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &x);
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    for(i=0;i<v.size()-2;i++)
    {
        for(j=i+1;j<v.size()-1;j++)
            cnt=cnt+BS(i,j);
    }
    printf("%d\n", cnt);
    return 0;
}