I'm getting TLE despite having an optimal time complexity: $$$O(nk)$$$ where $$$k$$$ is the target and $$$n$$$ is the number of coins. I even tried optimizing the modulo operation according to https://codeforces.com/blog/entry/77506, but I still have one test case that keeps TLE-ing. Further, downloading and running that test case locally indicates that my code is executing in well under the time limit of $$$1$$$ second.

Is there anything I can do at this point?

Submission: https://cses.fi/paste/6a1dc1e39bbd5552186afe/

Problem: https://cses.fi/problemset/task/1635

P.S. Tagging pllk in case this is an issue with the judging servers.

CSES submissions are not globally visible. You need to share it as a paste (you can create one by scrolling to the bottom of your code in your submission, or alternatively use an online paste website. Here's my solution as a paste for example: https://cses.fi/paste/3ff7373cf56f6af416e923/. please share yours the same way). If you're using an O(nk) memory solution, you are not being cache friendly most likely, which is why it might TLE.

Thanks for the heads up! I've updated the post.

Instead of taking MOD(

`dp[x]%MOD`

) directly try using`if(dp[x]>MOD) dp[x]-= MOD`

, this should definitely help, moreover if you are storing your dp values aslongthen you should store it asint.I've already implemented the MOD optimization you mentioned.

Changing long to int sounds like a good idea.

Update: changing long to int did the trick

Please can you explain how changing long into int decrease time?