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.
Instead of taking MOD(
dp[x]%MOD
) directly try usingif(dp[x]>MOD) dp[x]-= MOD
, this should definitely help, moreover if you are storing your dp values as long then you should store it as int.thanks, it works.
why TLE For this https://cses.fi/paste/c9b8bdf1ac11f0de582fcd/ ?