Submission #669807

#TimeUsernameProblemLanguageResultExecution timeMemory
669807rv4102Knapsack (NOI18_knapsack)C++17
17 / 100
4 ms1068 KiB
#include <iostream> #include <vector> using namespace std; int main(){ int capacity, n; cin >> capacity >> n; vector<int> price(n), weight(n), copies(n); for(int i=0; i<n; i++){ cin >> price[i] >> weight[i] >> copies[i]; } // dp[i][j] tells us the maximum profit we can achieve using // a subcollection of first i elements, with j weight vector<vector<int>> dp(n+1, vector<int>(capacity+1, 0)); for(int i=1; i<=n; i++){ for(int j=1; j<=min(2000, copies[i-1]); j++){ for(int k=1; k<=capacity; k++){ if(k >= weight[i-1]*j){ dp[i][k] = max(dp[i-1][k], dp[i-1][k-weight[i-1]*j] + price[i-1]*j); } else{ dp[i][k] = dp[i-1][k]; } } } } cout << dp[n][capacity] << endl; }
#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...