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?

Submission link

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();