Cod sursa(job #1196657)

Utilizator AndreiBarbutaAndrei Barbuta AndreiBarbuta Data 8 iunie 2014 17:20:31
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
#include <algorithm>
#define IN "nrtri.in","r",stdin
#define OUT "nrtri.out","w",stdout

const int MAX=1000;

using namespace std;

int cb(int st,int l1,int l2);

int v[MAX],n,cnt;

int main()
{
    freopen(IN);
    freopen(OUT);
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        scanf("%d",v+i);
    sort(v+1,v+n+1);
    for(register int i=1;i<=n;i++)
        for(register int j=i+1;j<=n;j++)
            cnt+=cb(j,v[i],v[j])-j;
    printf("%d",cnt);
    return 0;
}

int cb(int st,int l1,int l2){
    int dr=n,mij,sol=0;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]>l1+l2)
            dr=mij-1;
        else{
            sol=mij;
            st=mij+1;
        }
    }
    return sol;
}