Submission #576715

#	Time	Username	Problem	Language	Result	Execution time	Memory
576715		kalash04	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	1108 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ll MOD = 1e9 + 7;

struct item {
  int value;
  int weight;
  int copies;
};

vector<item> items;
vector<vector<int>> dp;

int knapsack(vector<item>& items, int i, int j) {
  if(i == items.size()) return 0;
  if(dp[i][j] != -1) return dp[i][j];
  if(j - items[i].weight >= 0) {
    if(items[i].copies > 0) {
      items[i].copies--;
      int a = knapsack(items, i, j - items[i].weight);
      items[i].copies++;
      int b = knapsack(items, i + 1, j);
      dp[i][j] = max({dp[i][j], a + items[i].value, b});
    } else {
      dp[i][j] = max(dp[i][j], knapsack(items, i + 1, j));
    }
  } else {
    dp[i][j] = max(dp[i][j], knapsack(items, i + 1, j));
  }
  return dp[i][j];
}

void solve() {
  int s, n;
  cin >> s >> n;
  items.resize(n);
  dp.resize(n + 1, vector<int>(s + 1, -1));
  for (int i = 0; i < n; i++) {
    cin >> items[i].value >> items[i].weight >> items[i].copies;
  }
  cout << knapsack(items, 0, s) << endl;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  cout.tie(NULL);
	solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'int knapsack(std::vector<item>&, int, int)':
knapsack.cpp:17:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   if(i == items.size()) return 0;
      |      ~~^~~~~~~~~~~~~~~

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