#include <bits/stdc++.h>
using namespace std;
const int maxn = 50002, maxs = 2001;
long long dp[maxn][maxs][2];
int main() {
int s, n;
struct item
{
int v, w, k;
};
cin >> s >> n;
struct item arr[n+1];
// v -> value
// w -> weight
// k -> copies
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
arr[i] = {a,b,c};
}
// we find that our dp array will have 3 dimensions of [n][w]
// at dp[i][j] -> we find the number of item i used to have a total value of j
long long ans = 0;
// practice with a 0-1 knapsack
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= s; j++)
{
/*
we must keep weight in mind
we must keep the number of uses of the current item in mind
a cell can either be reached from an earlier state in the same row or through the row above j
*/
dp[i][j][0] = dp[i-1][j][0];
if (j - arr[i].w >= 0) {
long long trans = dp[i-1][j-arr[i].w][0] + (long)arr[i].v;
if (trans >= dp[i][j][0])
{
dp[i][j][0] = trans;
dp[i][j][1] = 1;
}
}
if (j - arr[i].w >= 0 && dp[i][j-arr[i].w][1] < arr[i].k) {
long long trans = dp[i][j-arr[i].w][0] + (long)arr[i].v;
if (trans > dp[i][j][0])
{
dp[i][j][0] = trans;
dp[i][j][1] = dp[i][j - arr[i].w][1] + 1;
} else if (trans == dp[i][j][0] && dp[i][j-arr[i].w][1] + 1 < dp[i][j][1]) {
dp[i][j][1] = dp[i][j-arr[i].w][1] + 1;
}
}
ans = max(ans, dp[i][j][0]);
}
}
cout << ans << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3284 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3284 KB |
Output is correct |
6 |
Correct |
2 ms |
3296 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3284 KB |
Output is correct |
9 |
Correct |
2 ms |
3284 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3284 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3284 KB |
Output is correct |
6 |
Correct |
2 ms |
3296 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3284 KB |
Output is correct |
9 |
Correct |
2 ms |
3284 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Incorrect |
2 ms |
3284 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3284 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3284 KB |
Output is correct |
10 |
Correct |
2 ms |
3296 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3284 KB |
Output is correct |
13 |
Correct |
2 ms |
3284 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Incorrect |
2 ms |
3284 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3284 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3284 KB |
Output is correct |
10 |
Correct |
2 ms |
3296 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3284 KB |
Output is correct |
13 |
Correct |
2 ms |
3284 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Incorrect |
2 ms |
3284 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |