Submission #1133892

#TimeUsernameProblemLanguageResultExecution timeMemory
1133892Chal1shkanKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms1640 KiB
# include <bits/stdc++.h> using namespace std; # define ll long long # define ld long double # define pii pair <int, int> # define pll pair <ll, ll> # define nl '\n' # define sz(x) (int)(x).size() # define all(x) (x).begin(), (x).end() # define deb(x) cerr << #x << " = " << x << endl; # define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) const int maxn = (int)1e6 + 3; const ll inf = (ll)1e9 + 0; const int mod = (int)1e9 + 7; const bool T = 0; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int s, n; array<int, 3> a[maxn]; int dp[2][maxn]; void ma1n () { cin >> s >> n; for (int i = 1; i <= n; ++i) { cin >> a[i][0] >> a[i][1] >> a[i][2]; a[i][2] = min(a[i][2], s / a[i][1]); } bool cur = 1, prev = 0; for (int i = 1; i <= n; ++i) { for (int c = 1; c <= a[i][2]; ++c) { for (int j = s - a[i][1] * c; j >= 0; --j) { dp[cur][j + a[i][1] * c] = max(dp[cur][j + a[i][1] * c], dp[prev][j] + a[i][0] * c); } } for (int j = 0; j <= s; ++j) { dp[cur][j] = max(dp[cur][j], dp[prev][j]); dp[prev][j] = 0; } swap(prev, cur); } cout << dp[prev][s] << nl; } signed main () { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int ttt = 1; if (T) cin >> ttt; while (ttt--) { ma1n(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...