In this problem, https://mirror.codeforces.com/contest/1433/problem/F, instead of doing the holistic n^4 dp, i instead did a n^3 dp for every row, effectively(n^4 anyway), however I am wondering if this subproblem can be solved in faster than n^3? The question is this, given an array of n integers, what is the maximum sum i can make of each modulo k without taking more than x items, my dp was 3d where dp[i][j][cnt] was the best answer with the first i numbers, that was congruent to to j mod k and used cnt items — so the complexity was O(n*k*x), but i cant help but wonder if there is a faster way to do it? Would that just reduce to np complete? I'm very curious.