Hello all,

I've been trying to solve this problem, and even after reading the editorial, I'm unable to get an AC.

My submission: https://mirror.codeforces.com/contest/505/submission/85055307

My approach:

So, if anyone has solved the problem, they know that there are only 491 total types of jumps possible, at any point. That is d-245,d-244,d-243,...,d,d+1,...,d+245. So I've created dp[i][j], where i is the current point, and j is the last modified jump size (mjs), where dp[i][j] would give the maximum number of gems collected, with being at point i with the last jump of size j.

Since d is in the range 0 to 30000, that'd mean that d-245,...,d+245, will be in the same order. So to deal with that, $$$mjs = jumsize-d+offset$$$. Here, $$$offset=250$$$.

Similarly I've create a boolean matrix visited[i][j], with the same system in place.

Now I go from 0 to MAXN (MAXN = 3e4+5). Initialising dp[d][offset] = gems[d], and visited[d][offset] = true.

Now for each point, we go forward.

So, if we reached point i with a jump mjs, then we can take jumps of mjs-1, mjs and mjs+1. So we simply update these values if possible.

Great! That's pretty much it. So, now my submission is failing on Test Case 4, which it misses by 1. I checked all the smaller test cases, which were shown completely, and my code worked fine on them.

So, I'd like to ask two things here: 1. How do you deal with such a situation? If you don't have any tests to test your code, and you know that there is some bug. 2. What's the catch here? I couldn't find anything obvious. I tried to play around the code a bit, but that didn't do anything.

Any kind of advice is highly appreciated. Please help me understand how you people deal with such situations. If you also find the bug, then that's a plus.