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://mirror.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.

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.thanks, it works.

Thanks it works.

public class CoinCombinationsI { public static long mod = 1000000007L;

} }

Another possiblity is to to keep

`dp`

as a`long[]`

, and then have a single`%`

-operation after the coin for loopThis should cut down the number of

`%`

-operations by a factor of 100 compared to your original code.why TLE For this https://cses.fi/paste/c9b8bdf1ac11f0de582fcd/ ?