Cod sursa(job #576965)

Utilizator biroBiro Alexandru biro Data 9 aprilie 2011 17:28:51
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<algorithm>

using namespace std;

int n , nr=0 ;
int v[802] ;
int k;

int cb(int a) {
  int pas=1<<9,i;
  for(i=0;pas;pas/=2) {
    if (i+pas<=n && v[i+pas]<=a)
      i+=pas;
  }
  return i;
}

int main() {
  freopen ("nrtri.in","r",stdin);
  freopen ("nrtri.out","w",stdout);
  
  scanf("%d" , &n );
  for (int i=1 ; i<=n ; i++) {
    scanf("%d",&v[i]);
  }
  sort(v+1,v+1+n);
  for (int i=1 ; i<n ; i++) {
    for (int j=i+1 ; j<=n ; j++) {
      k=cb(v[i]+v[j]);
      nr=nr+(k-j);
    }
  }
  printf("%d",nr);
  
  return 0 ;
}