# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
484681 | 2021-11-05T03:47:29 Z | Ncode | Knapsack (NOI18_knapsack) | C++17 | 278 ms | 259648 KB |
#include <bits/stdc++.h> using namespace std; int dp[20005][20005]; const int inf = 1e9+5; int main(){ int S, n; cin>>S>>n; int v, w, k; vector<pair<int, int>> a; for(int i=0;i<n;i++){ cin>>v>>w>>k; while(k--) a.push_back({v, w}); } // for(int i=0;i<n;i++){ // for(int j=0;j<=S;j++){ // dp[i][j] = inf; // } // } dp[0][0] = 0; for(int i=0;i<a.size();i++){ for(int sum = S; sum >= 0; sum --){ dp[i][sum] = dp[i-1][sum]; if(sum >= a[i].second && dp[i-1][sum - a[i].second] + a[i].first > dp[i][sum]){ dp[i][sum] = dp[i-1][sum - a[i].second] + a[i].first; } } } // for(int i=0;i<n;i++){ // for(int j = 0; j<=S; j++){ // cout<<dp[i][j]<<" "; // }cout<<endl; // } cout<<dp[a.size() - 1][S]<<'\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 278 ms | 259648 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 716 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 716 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 278 ms | 259648 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 278 ms | 259648 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |