Cod sursa(job #930539)

Utilizator AeroHHorea Stefan AeroH Data 27 martie 2013 18:20:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 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+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);       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; }