My solution has time complexity O(n^3) and I have taken a look at the editorial, it also has the same time complexity, however, my solution cannot pass the time limit. Can someone give me some hint about this?
Solution
PrintWriter out = new PrintWriter(System.out);
Scanner in = new Scanner();
int n = in.nextInt();
int m = in.nextInt();
int b = in.nextInt();
MOD = in.nextInt();
int[] data = new int[n];
for (int i = 0; i < n; i++) {
data[i] = in.nextInt();
}
dp = new int[2][n][b + 1];
int cur = 1;
for (int i = n - 1; i >= 0; i--) {
if (i + 1 < n) {
for (int j = 0; j <= b; j++) {
dp[0][i][j] += dp[0][i + 1][j];
dp[0][i][j] %= MOD;
}
}
if (data[i] <= b) {
dp[0][i][data[i]]++;
dp[0][i][data[i]] %= MOD;
}
}
for (int i = 1; i < m; i++) {
for (int j = n - 1; j >= 0; j--) {
for (int k = b; k >= 0; k--) {
dp[cur][j][k] = 0;
if (j + 1 < n) {
dp[cur][j][k] += dp[cur][j + 1][k];
dp[cur][j][k] %= MOD;
}
if (k + data[j] <= b) {
dp[cur][j][k + data[j]] += dp[1 - cur][j][k];
dp[cur][j][k + data[j]] %= MOD;
}
}
}
cur = 1 - cur;
}
long result = 0;
for (int i = 0; i <= b; i++) {
result += dp[1 - cur][0][i];
result %= MOD;
}
out.println(result);
out.close();
Reduce modulo operations.
If you have to use modulo, write:
while(dp[cur][j][k] > MOD) dp[cur][j][k] -= MOD;
Thanks, work like a charm :)