# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1086686 | quangminh412 | Knapsack (NOI18_knapsack) | C++14 | 1 ms | 604 KiB |
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;
#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const int maxn = 1e5 + 9;
ll s;
int n;
ll v[maxn], w[maxn], k[maxn];
int main()
{
if (fopen("BALO.INP", "r"))
{
freopen("BALO.INP", "r", stdin);
freopen("BALO.OUT", "w", stdout);
}
faster();
cin >> s >> n;
// bool sub2 = true;
// for (int i = 1; i <= n; i++)
// {
// cin >> v[i] >> w[i] >> k[i];
// if (k[i] != 1) sub2 = false;
// }
//
// if (n == 1)
// {
// ll num = s / w[1];
// cout << min(k[1], num) * v[1] << '\n';
//
// return 0;
// } else
// if (sub2 == true)
// {
// vector<vector<ll>> dp(n + 5, vector<ll>(s + 5, 0));
// ll ans = 0;
// for (int i = 1; i <= n; i++)
// for (int j = 0; j <= s; j++)
// {
// dp[i][j] = dp[i - 1][j];
// if (j - w[i] >= 0)
// dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
// if (i == n) ans = max(ans, dp[i][j]);
// }
// cout << ans << '\n';
//
// return 0;
// }
ll ans = 0;
vector<vector<ll>> dp(n + 5, vector<ll>(s + 5, 0));
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= s; j++)
{
dp[i][j] = dp[i - 1][j];
for (int c = 1; c <= min(s / w[i], k[i]); c++)
if (j >= c * w[i])
dp[i][j] = max(dp[i][j], dp[i - 1][j - c * w[i]] + c * v[i]);
if (i == n) ans = max(ans, dp[i][j]);
}
}
cout << ans << '\n';
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... |