Cod sursa(job #903549)

Utilizator valiro21Valentin Rosca valiro21 Data 1 martie 2013 22:09:05
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>
#define NMax 30001

using namespace std;

long n,vmin[NMax+NMax],v[NMax],minn,maxx,rez;

int bsearchMin(long in,long fn,long v[],long val) {
    long mid;
    if(v[fn]<=val)
        return fn;
    else
        if(val<v[1])
            return 0;

    while(in<=fn) {
        mid=(fn-in)/2+in;
        if(val<v[mid])
            fn=mid-1;
        else
            in=mid;
    }
    return mid;
}

bool comp(long a,long b) {
    if(a<=b)
        return 1;
    return 0;
}

int main()
{
    freopen("nrtri.in","rt",stdin);
    freopen("nrtri.out","wt",stdout);
    scanf("%ld",&n);
    for(long i=1;i<=n;i++)
        scanf("%ld",&v[i]);

    sort(v+1,v+n+1,comp);

    for(long i=0;i<=NMax+NMax;i++) {
        vmin[i]=bsearchMin(1,n,v,i);
    }

    for(long i=1;i<n;i++)
        for(long j=i+1;j<=n;j++) {
            maxx=vmin[v[j]+v[i]];
            rez+=maxx-j > 0 ? maxx-j : 0;
        }

    printf("%ld\n",rez);

    return 0;
}