Submission #1219413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219413		alessandrojean	Knapsack (NOI18_knapsack)	C++20	73 / 100	154 ms	327680 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

const int MAX_N = 100000;
const int MAX_S = 2000;

int S;
int N;
int * V; // int V[MAX_N];
int * W; // int W[MAX_N];
int * K; // int K[MAX_N];
int dp[MAX_N][MAX_S + 1];

class MaxQueue {
  private:
    deque<pair<int, int>> Q;
    int time_added;
    int time_removed;
    int delta;

  public:
    MaxQueue() {
      delta = time_added = time_removed = 0;
    }

    void push(int x) {
      int x_delta = x - delta;

      while (!Q.empty() && Q.back().first < x_delta) {
        Q.pop_back();
      }

      Q.push_back({x_delta, time_added++});
    }

    void pop() {
      if (Q.empty()) {
        return;
      }

      if (time_removed == Q.front().second) {
        Q.pop_front();
      }

      time_removed++;
    }

    int max() {
      return Q.front().first + delta;
    }

    void add_all(int d) {
      delta += d;
    }
};

/**
 * Difícil achar referências que usem a fila do jeito que foi passado em aula,
 * mas estes links comentam da ideia da janela deslizante.
 * 
 * Referências:
 * - https://cp-algorithms.com/dynamic_programming/knapsack.html
 * - https://books.google.com.br/books?id=u5DB7gck08YC&lpg=PA211&pg=PA194&redir_esc=y#v=onepage&q&f=false
 * - https://dhruvbird.blogspot.com/2011/09/integer-01-bounded-knapsack-problem.html
 * - https://blog.mitrichev.ch/2011/07/integral-bounded-knapsack-problem.html
 * - https://programming.vip/docs/monotone-queue-optimization-for-multiple-knapsack-problems.html
 */
int find_best_solution_sliding_window() {
  for (int i = N - 1; i >= 0; i--) {
    // Itera sobre todos as possíveis classes de W[i]. Vai só até W[i] - 1
    // pois sempre vai ter um rest e um mult tal que color + mult * W[i] = S.
    for (int color = 0; color < W[i]; color++) {
      // Cada classe tem sua fila.
      MaxQueue queue;
      int window_size = 0;

      // Itera entre os próximos casos da mesma classe.
      for (int mult = 0; color + mult * W[i] <= S; mult++) {
        queue.add_all(V[i]);
        queue.push(dp[i + 1][color + mult * W[i]]);

        // Chegou ao limite de itens, precisa avançar a janela.
        if (++window_size > K[i] + 1) {
          queue.pop();
          window_size--;
        }

        dp[i][color + mult * W[i]] = queue.max();
      }
    }
  }

  return dp[0][S];
}

int main(int argc, char * argv[]) {
  cin >> S >> N;

  V = new int[N];
  W = new int[N];
  K = new int[N];

  for (int i = 0; i < N; i++) {
    cin >> V[i] >> W[i] >> K[i];
  }

  cout << find_best_solution_sliding_window() << '\n';

  delete [] V;
  delete [] W;
  delete [] K;

  return EXIT_SUCCESS;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27