Submission #481081

#	Time	Username	Problem	Language	Result	Execution time	Memory
481081		chuangsheep	Knapsack (NOI18_knapsack)	C++11	100 / 100	135 ms	125764 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#define allr(x, r) begin(x), begin(x) + (r)
#define mp make_pair

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

int main()
{
#if defined(DEBUG) && !defined(ONLINE_JUDGE)
  // DEBUG
  cerr << "DEBUG flag set - see test.out for output\n";
  freopen("/home/chuang/shared-drives/F:/repos/cp/ois/noi2018/test.in", "r", stdin);
  freopen("/home/chuang/shared-drives/F:/repos/cp/ois/noi2018/test.out", "w", stdout);
#else
  cin.tie(0)->sync_with_stdio(false);
#endif

  int S, N;
  cin >> S >> N;

  vector<vector<pi>> items(S + 1, vector<pi>());

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

  for (int i = 0; i <= S; i++)
    sort(all(items[i]), greater<pi>());

  int total = 0;
  for (int i = 1; i <= S; i++)
    total += S / i;

  vector<vi> dp(total + 1, vi(S + 1, 0));
  int n_i = 1;
  for (int w = 1; w <= S; w++)
  {
    if (items[w].size() == 0)
      continue;
    int w_i = 0, w_c = items[w][0].second;
    for (int num = 0; num < S / w; num++)
    {
      for (int c = 1; c <= S; c++)
      {
        dp[n_i][c] = dp[n_i - 1][c];
        if (c - w >= 0)
          dp[n_i][c] = max(dp[n_i][c], dp[n_i - 1][c - w] + items[w][w_i].first);
      }
      n_i++;
      w_c--;
      if (w_c == 0)
      {
        w_i++;
        if (w_i >= items[w].size())
          break;
        w_c = items[w][w_i].second;
      }
    }
  }

  cout << dp[n_i - 1][S] << "\n";

  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (w_i >= items[w].size())
      |             ~~~~^~~~~~~~~~~~~~~~~~

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