# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
851990 |
2023-09-21T04:14:12 Z |
Jere |
Knapsack (NOI18_knapsack) |
C++17 |
|
172 ms |
262144 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Item {
int value, weight, copies;
// Default constructor
Item() {
value = 0;
weight = 0;
copies = 0;
}
Item(int value, int weight, int copies) {
this->value = value;
this->weight = weight;
this->copies = copies;
}
};
int knapsack(int S, int N, Item arr[]) {
vector<vector<int>> dp(N + 1, vector<int>(S + 1, 0));
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= S; j++) {
dp[i][j] = dp[i - 1][j]; // Initialize with the previous row's value
// Consider multiple copies of the same item
for (int k = 1; k <= arr[i - 1].copies && k * arr[i - 1].weight <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * arr[i - 1].weight] + k * arr[i - 1].value);
}
}
}
return dp[N][S];
}
int main() {
int S, N;
cin >> S >> N;
Item arr[N];
for (int i = 0; i < N; i++) {
int value, weight, copies;
cin >> value >> weight >> copies;
arr[i] = Item(value, weight, copies); // Initialize the Item array
}
int result = knapsack(S, N, arr);
cout << result << endl; // Print the maximum total value
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
1116 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
3 ms |
1112 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1112 KB |
Output is correct |
15 |
Correct |
1 ms |
1116 KB |
Output is correct |
16 |
Correct |
1 ms |
1116 KB |
Output is correct |
17 |
Correct |
1 ms |
1116 KB |
Output is correct |
18 |
Correct |
1 ms |
1116 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
1116 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1116 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1116 KB |
Output is correct |
12 |
Correct |
1 ms |
1112 KB |
Output is correct |
13 |
Correct |
1 ms |
1116 KB |
Output is correct |
14 |
Correct |
1 ms |
1116 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
1112 KB |
Output is correct |
17 |
Correct |
1 ms |
1112 KB |
Output is correct |
18 |
Correct |
1 ms |
1112 KB |
Output is correct |
19 |
Correct |
1 ms |
1116 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
1 ms |
1116 KB |
Output is correct |
22 |
Correct |
1 ms |
1116 KB |
Output is correct |
23 |
Correct |
1 ms |
1112 KB |
Output is correct |
24 |
Correct |
1 ms |
1116 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
172 ms |
1208 KB |
Output is correct |
27 |
Correct |
1 ms |
1112 KB |
Output is correct |
28 |
Correct |
1 ms |
1112 KB |
Output is correct |
29 |
Correct |
1 ms |
1116 KB |
Output is correct |
30 |
Correct |
2 ms |
1116 KB |
Output is correct |
31 |
Correct |
1 ms |
1116 KB |
Output is correct |
32 |
Correct |
1 ms |
1116 KB |
Output is correct |
33 |
Correct |
1 ms |
1112 KB |
Output is correct |
34 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
1116 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1116 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1116 KB |
Output is correct |
12 |
Correct |
1 ms |
1112 KB |
Output is correct |
13 |
Correct |
1 ms |
1116 KB |
Output is correct |
14 |
Correct |
1 ms |
1116 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
1112 KB |
Output is correct |
17 |
Correct |
1 ms |
1112 KB |
Output is correct |
18 |
Correct |
1 ms |
1112 KB |
Output is correct |
19 |
Correct |
1 ms |
1116 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
1 ms |
1116 KB |
Output is correct |
22 |
Correct |
1 ms |
1116 KB |
Output is correct |
23 |
Correct |
1 ms |
1112 KB |
Output is correct |
24 |
Correct |
1 ms |
1116 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
172 ms |
1208 KB |
Output is correct |
27 |
Correct |
1 ms |
1112 KB |
Output is correct |
28 |
Correct |
1 ms |
1112 KB |
Output is correct |
29 |
Correct |
1 ms |
1116 KB |
Output is correct |
30 |
Correct |
2 ms |
1116 KB |
Output is correct |
31 |
Correct |
1 ms |
1116 KB |
Output is correct |
32 |
Correct |
1 ms |
1116 KB |
Output is correct |
33 |
Correct |
1 ms |
1112 KB |
Output is correct |
34 |
Correct |
1 ms |
1116 KB |
Output is correct |
35 |
Correct |
51 ms |
6996 KB |
Output is correct |
36 |
Runtime error |
151 ms |
262144 KB |
Execution killed with signal 9 |
37 |
Halted |
0 ms |
0 KB |
- |