fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5.  
  6.  
  7.  
  8. int main()
  9. {
  10.     int n,i,j,k,low,high,mid;
  11.     int sticks[2000],c,counter,key;
  12.     scanf("%d",&n);
  13.     while(n!=0){
  14.             c=((n)*(n-1)*(n-2))/6;
  15.             counter=0;
  16.         for(i=0;i<n;i++){
  17.             scanf("%d",&sticks[i]);
  18.         }
  19.         sort(sticks,sticks+n);
  20.         for(i=0;i<n-2;i++){
  21.             for(j=i+1;j<n-1;j++){
  22.                 key=sticks[i]+sticks[j];
  23.                 low=j+1;
  24.                 high=n-1;
  25.                 while(low<=high){
  26.                     mid=(low+high)/2;
  27.                     if(key==sticks[mid]){
  28.                             low=mid;
  29.                         while(sticks[low]==key)
  30.                         low++;
  31.                     }
  32.                     else if(key>sticks[mid])
  33.                         low = mid+1;
  34.                     else
  35.                         high = mid-1;
  36.                 }
  37.                 counter = counter + (low-j-1);
  38.             }
  39.         }
  40.         //printf("c -> %ld\n",c);
  41.         //printf("counter -> %ld\n",counter);
  42.         printf("%d\n",c-counter);
  43.         scanf("%d",&n);
  44.     }
  45.     return 0;
  46. }
  47.  
  48.  
Time limit exceeded #stdin #stdout 5s 2728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5pl7af
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!