# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1135927 | ashokanr | Knapsack (NOI18_knapsack) | C++20 | 48 ms | 3568 KiB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int dp[N];
vector <int> W,V;
vector <int> v[2005];
struct mitt
{
int v,w,k;
bool operator < (const mitt &tim)
{
return v > tim.v;
}
} a[N];
main()
{
ios_base::sync_with_stdio(0);
int n,s;
cin >> s >> n;
for(int i=1;i<=n;++i)
{
cin >> a[i].v >> a[i].w >> a[i].k;
}
sort(a+1,a+1+n);
W.push_back(0);
V.push_back(0);
for(int i=1;i<=n;i++)
{
while (a[i].k-- && v[a[i].w].size() <= s / a[i].w)
v[a[i].w].push_back(a[i].v);
}
for(int w=1;w<=s;w++)
{
for(auto x:v[w])
{
W.push_back(w);
V.push_back(x);
}
}
// for(auto x:W) cout << x << " ";
// cout << endl;
// for(auto x:V) cout << x << " ";
for(int i=1;i<=W.size()-1;++i)
{
for(int j=s;j;--j)
{
if (j >= W[i]) dp[j] = max(dp[j],dp[j-W[i]] + V[i]);
}
}
cout << *max_element(dp,dp+s+1);
}
Compilation message (stderr)
# | 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... |