Блог пользователя alibaba

Автор alibaba, 9 лет назад, По-английски

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();
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Reduce modulo operations.

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