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

Автор thequacker, история, 4 часа назад, По-английски

Problem Link(might not work)

Problem Statement URL

My solution which gives MLE on tc 11


int n, W; cin >> n >> W; vi w(n + 1), v(n + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; vvi dp(n + 1, vi(W + 1, 0)); for (int i = n; i >= 1; i--) { for (int weight = 0; weight <= W; weight++) { int exclude = 0; if (i + i <= n) exclude = dp[i + i][weight]; int include = 0; if (w[i] <= weight) { include = v[i]; for (int jump = i; i + jump <= n; jump += i) { if (weight >= w[i]) { include = max(include, v[i] + dp[i + jump][weight - w[i]]); } } } dp[i][weight] = max(include, exclude); } } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, dp[i][W]); } cout << ans << "\n";

How to solve it? ;)

image added if the link is not accesible(wrong spelling nvm)

Problem Statement URL

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
4 часа назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

It says I am not allowed to view the contest.

I think what you need to do is reduce the size of your dp array. To calculate values of dp[i] you only use dp[i-1]. You can throwaway the older values. This is called the "alternating row trick" sometimes because to calculate one row of the dp matrix you only need the previous one.

  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    but since the problem requires us to jump only in such forms i ... i+i .... i+2*i so i don't think that is possible

    • »
      »
      »
      3 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is the contest ongoing? If so, you are not allowed to ask for help. If not, please share proof that it isn't from an ongoing contest.

      • »
        »
        »
        »
        2 часа назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        no,it is over, it was yesterday, if you aren't sure then you can maybe help me few hours later :)

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by thequacker (previous revision, new revision, compare).

»
4 часа назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted

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

Come to 301 when you will be free, I will explain why there is MLE.