This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int s,n,ans;
int dp[2005][2005];
struct item
{
int val,weight,cnt;
};
item a[100005];
vector<int> p[2005];
bool comp(item a, item b)
{
return (a.weight < b.weight or (a.weight == b.weight and a.val > b.val));
}
int main()
{
cin>>s>>n;
for (int i = 1; i <= n; i++)
{
cin>>a[i].val>>a[i].weight>>a[i].cnt;
}
sort(a+1,a+1+n,comp);
for (int i = 1; i <= n; i++)
{
int w=a[i].weight,k=a[i].cnt;
while (p[w].size() < (s/w) and k > 0)
{
if (!p[w].empty()) p[w].push_back(a[i].val + p[w].back());
else p[w].push_back(a[i].val);
k--;
}
}
for (int i = 1; i <= s; i++)
{
for (int j = 1; j <= s; j++)
{
dp[i][j]=dp[i-1][j];
for (int cnt = 0; cnt < p[i].size(); cnt++)
{
if (j - (cnt + 1)*i < 0) continue;
dp[i][j]=max(dp[i][j],dp[i-1][j-(cnt+1)*i] + p[i][cnt]);
}
ans=max(ans,dp[i][j]);
}
}
// for (int i = 1; i <= s; i++) cout<<p[i].size()<<' ';cout<<endl;
// for (int i = 1; i <= s; i++)
// {
// for (int j = 1; j <= s; j++)
// {
// cout<<dp[i][j]<<' ';
// }
// cout<<endl;
// }
cout<<ans;
}
Compilation message (stderr)
knapsack.cpp: In function 'int main()':
knapsack.cpp:26:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
26 | while (p[w].size() < (s/w) and k > 0)
| ~~~~~~~~~~~~^~~~~~~
knapsack.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int cnt = 0; cnt < p[i].size(); cnt++)
| ~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |