Cod sursa(job #930583)

Utilizator AeroHHorea Stefan AeroH Data 27 martie 2013 18:46:47
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <algorithm>
 using namespace std;
   long n,vmin[60001],v[30001],minn,maxx,rez,NMAX;
     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+1;
            if(val<v[mid])
                fn=mid-1;
            else
                in=mid;
            }
               return fn;
}
 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);
        NMAX=v[n]+v[n-1];
         for(long i=0;i<=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; }