2nd TC giving run error! in the subset sum to target problem

#1

my sol : https://ide.codingblocks.com/s/251176

ques : https://hack.codingblocks.com/app/contests/1463/370/problem

i am not able to find out the reason for the run error.
according to me the code is fine !

#2

@saarthakseth
Your code is giving runtime error because you have tried to create an array of large size during runtime. See maximum value of n is 10^5 and k is 5000. In your code you have tried to create dp[n+1][k+1], for maximum value of n and k it become dp[100001][5001] which can’t be possible. We don’t have that much memory allocated for such question. Try recursion to solve this question.

#3

can u tell me how to optimize my dp sol in terms of space ??

#4

i’ve used dp, recursion will give tle

#5

@saarthakseth
Change line 7 in your code with these line, your code will work
bool *dp = new bool[n+1];
for(int i=0;i<=n;i++) {
dp[i] = new bool[k+1];
}

#6

@saarthakseth There is problem with static allocation of memory. Dynamic allocation will work. See above reply.

#7

oh… thnx for the advice it passed all TCs now

#8

btw it should have been bool ** dp = new bool*[n+1]

#9

this is the problem with cb online judge only right ??

#10

or had it given run error in other online judges like codeforces, etc too ?

#11

@saarthakseth
It might give same runtime error on other platform as well. It depends on constraints and memory limit given. Please mark this doubt as resolved.