#include <bits/stdc++.h>
using namespace std;
typedef struct item item;
struct item
{
unsigned w;
unsigned v;
unsigned k;
};
bool item_cmp(item a, item b)
{
if (a.w < b.w)
return 1;
else if (b.w < a.w)
return 0;
else
{
if (a.v < b.v)
return 1;
else
return 0;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
unsigned s, n;
cin >> s >> n;
vector<item> items(n);
for (size_t i = 0; i < n; i++)
{
item &x = items[i];
cin >> x.v >> x.w >> x.k;
}
sort(items.begin(), items.end(), item_cmp);
vector<unsigned> cost;
vector<unsigned> value;
auto it = --items.end();
for (unsigned w = s; w > 0; w--)
{
unsigned incl = s / w + 1;
while (incl && it != --items.begin() && it->w == w)
{
cost.push_back(it->w);
value.push_back(it->v);
incl--;
if (it->k > 1)
it->k--;
else
it--;
}
}
vector<vector<unsigned>> dp(cost.size(), vector<unsigned>(s + 1, 0));
for (unsigned i = cost[0]; i < s + 1; i++)
dp[0][i] = value[0];
for (size_t i = 1; i < cost.size(); i++)
{
for (size_t j = 1; j < s + 1; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= cost[i] && dp[i - 1][j - cost[i]] + value[i] > dp[i][j])
dp[i][j] = dp[i - 1][j - cost[i]] + value[i];
}
}
cout << dp[cost.size() - 1][s] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |