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>
#define ll long long
using namespace std;
int main()
{
int s, n;
cin >> s >> n;
int val[n], wei[n], mult[n];
for (int i = 0; i < n; i++)
cin >> val[i] >> wei[i] >> mult[i];
ll dp[2][s + 1];
int fr = 0, sc = 1;
dp[0][0] = 0;
for (int j = 1; j <= s; j++)
{
dp[0][j] = 0;
if (wei[0] <= j)
{
dp[0][j] = (ll)min(j / wei[0], mult[0]) * (ll)val[0];
}
}
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= s; j++)
{
dp[sc][j] = dp[fr][j];
for (int m = 1; m <= mult[i] && j >= wei[i] * m; m++)
dp[sc][j] = max(dp[sc][j], dp[fr][j - wei[i] * m] + (ll)val[i] * (ll)m);
}
swap(fr, sc);
}
cout << dp[fr][s] << endl;
}
# | 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... |