# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1216561 | dragon28102008 | Knapsack (NOI18_knapsack) | C++17 | 345 ms | 327680 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define IN "main.inp"
#define OUT "main.out"
#define AC ios_base::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);
const ll mod = 998244353;
ll s , n;
vector<ll> v , w , k;
ll sub1()
{
ll res = min(k[0] ,(s/w[0] ) ) * v[0];
return res;
}
ll sub23()
{
vector<pair<ll,ll>> a;
for(ll i = 0 ; i<n ; i++)
{
for(ll j = 0 ; j<k[i] ; j++)
{
a.push_back({v[i] , w[i]});
}
}
vector<ll> dp(s+1 , 0);
for(pair<ll,ll> p: a)
{
for(ll i = s ; i>=p.second ; i--)
{
dp[i] = max(dp[i] , dp[i-p.second] + p.first);
}
}
return dp[s];
}
int main()
{
if (fopen(IN, "r"))
{
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
}
AC
cin>>s>>n;
v.resize(n);
w.resize(n);
k.resize(n);
for(ll i = 0 ; i<n ; i++)
{
cin>>v[i]>>w[i]>>k[i];
}
if(n == 1) cout<<sub1();
else cout<<sub23();
return 0;
}
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... |