Hi,
can any 1 help me solve this problem:
http://www.spoj.pl/problems/NOTATRI/
my code exceedes the timelimit..
i used this
1.sorted the data using quicksort
2.then used bruteforce
here is my code: (wont compile becoz i omitted the procedure for quicksort)
Code:
#include<stdio.h>
int main()
{
int i=0,j=0,k=0,n,ans=0,sum;
int arr[2001];
while(1)
{
scanf("%d",&n);
if(n==0) break;
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
quicksort(arr,0,n-1);
for(i=0;i<n-2;i++)
{
for(j=i+1;j<n-1;j++)
{
sum=arr[i]+arr[j];
for(k=j+1;k<n;k++)
{
if(sum<arr[k])
{
ans=ans+(n-k);
break;
}
}
}
}
printf("%d\n",ans);
ans=0;
}
return 0;
}
thanks