Submission #1177363

#TimeUsernameProblemLanguageResultExecution timeMemory
1177363satyanshuKnapsack (NOI18_knapsack)C++20
73 / 100
153 ms327680 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353; const ll INF = 1e18 + 7; void solve() { ll s, n; cin >> s >> n; vector<ll> v(n), w(n), k(n); for (int i = 0; i < n; i++) { cin >> v[i] >> w[i] >> k[i]; } if (n == 1) { cout << v[0] * min(s / w[0], k[0]) << endl; return; } vector<vector<ll>> dp(n, vector<ll>(s + 1)); // dp[i][j] = max value which she can get until ind i and remaining weight is j // base case:- dp[0][j] = (j/w[0])*v[0] dp[i][0] = 0; for (int j = 0; j <= s; j++) { dp[0][j] = min(j / w[0], k[0]) * v[0]; } for (int i = 1; i < n; i++) { for (int j = 0; j <= s; j++) { dp[i][j] = dp[i - 1][j]; for (int x = 1; x <= k[i] && x * w[i] <= j; x++) { dp[i][j] = max(dp[i][j], dp[i - 1][j - x * w[i]] + x * v[i]); } } } cout << dp[n - 1][s] << endl; return; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; t = 1; while (t--) { solve(); } 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...