alibaba's blog

By alibaba, 9 years ago, In English

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();
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Reduce modulo operations.

If you have to use modulo, write: while(dp[cur][j][k] > MOD) dp[cur][j][k] -= MOD;