Not Getting ac in Calvins Game, please help.

general
,
1

I have been trying to solve Calvins Game problem, but I am getting wrong ans and I am not able to figure out what is wrong in my logic.
Here is the link to my code, please help.

2

Fine i am posting this since answers are available on the internet and there s no rules for this contest as such and there s no reply for my previous query.

n,k=map(int,input().split())
a=list(map(int,input().split()))
arr=[-999999999999999]*n
k-=1
if(k+1<n):
   arr[k+1]=a[k+1]
if(k+2<n):
   arr[k+2]=max(a[k+2],arr[k+1]+a[k+2])
for i in range(k+3,n):
   arr[i]=max(arr[i],arr[i-2]+a[i],arr[i-1]+a[i])
arr[n-2]=max(arr[n-1]+a[n-2],arr[n-2])
for i in range(n-3,k,-1):
   arr[i]=max(arr[i],arr[i+2]+a[i],arr[i+1]+a[i])
if(k==n-1):
   arr[n-2]=a[n-2]
   arr[n-1]=0
if(k==n-2):
   arr[n-1]=a[n-1]
   arr[n-2]=max(0,arr[n-1]+a[n-2])
if(arr[k]<0):
   arr[k]=0
for i in range(min(k,n-3),-1,-1):
   arr[i]=max(arr[i],arr[i+2]+a[i],arr[i+1]+a[i])
print(arr[0])

Use simple DP. Initialize arr with all minimum values. Then find the arr[i] represents the maximum value of reaching that position . First run from k to n.Then come back from n to 1. And arr[i] is arr[i]=max(arr[i],arr[i-2]+a[i],arr[i-1]+a[i]) while going front and arr[i]=max(arr[i],arr[i+2]+a[i],arr[i+1]+a[i]) while coming back from n-1.Special conditions for arr[n-1] and arr[n-2] have been given to avoid SEGMENTATION fault. Furthermore while coming back if arr[k]<0 no need to traverse right at all you can go left starting itself, so set arr[k]=0.

for codes visit:-THIS LINK

PLEASE UPVOTE AND FOLLOW FOR ANY QUERIES IF U FIND IT HELPFUL.

1 Like
3

@anirudhjarvis
It would be better if you can tell me what is wrong with my code.

4

Its not loading in pastebin. Send me the link in ideone.

5

@anirudhjarvis

6

5 1
5 3 -2 -1 -1

For this input output should be 10 but ur program prints output as 8.
as go from 1 to 2 to 4 to 2 to 1. ANSWER = 10 not 8. FOLLOW MY PREVIOUS ANSWER DP APPROACH U’LL CORRECT UR ERROR.Essentially both LOGIC IS SAME just see my code and tweak ur code as ur DP is slightly wrong.(You should not traverse just from maxscore, traverse from back totally like me.See my code,approach and do it.)

PLEASE UPVOTE MY ANSWER AND ACCEPT IT AND FOLLOW FOR ANY QUERIES IF U FIND IT HELPFUL.

7

@anirudhjarvis

Still failing three test cases, please help. Below is the link.

https://pastebin.com/8D6AUdjn