i tried to solve the problem on spoj https://www.spoj.pl/problems/TRT/
the problem is based on DP
i coded the problem as ----
#include<iostream>
#include<algorithm>
#include<cstdio>
int arr[2000];
int main()
{
int i,l,r,age=1,n,sum=0;
scanf("%d",&n);
l=0,r=n-1;
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(i=0;i<n;i++)
{
if(arr[l]<=arr[r])
{
sum+=arr[l]*age;
l++;
age++;
}
else
{
sum+=arr[r]*age;
r--;
age++;
}
}
printf("%d\n",sum);
return 0;
}
but i am getting WA on submission....
Actually my code fails on some of the test cases like
INPUT-
6
21
31
12
3
4
33
The algorithm i use would give 349 (21*1 + 31*2 + 12*3 + 3*4 + 4*5 + 33*6)
as the answer.
But the correct answer is 389 with sequence of picking as(33, 4, 3, 12, 21,
31).
plz help me improve my algorithm !!
thanking in advance
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
