Submission #583765

#TimeUsernameProblemLanguageResultExecution timeMemory
583765jack715Knapsack (NOI18_knapsack)C++14
73 / 100
1083 ms7064 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define pp pop_back #define mp make_pair #define bb back #define ff first #define ss second #define int long long using namespace std; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("tmp.in", "r", stdin); // freopen("tmp.out", "w", stdout); int s, n; cin >> s >> n; vector<vector<int> > nums(n, vector<int>(3)); for (int i = 0; i < n; i++) { for (int j = 0; j < 3; j++) cin >> nums[i][j]; } int dp[2005]; memset(dp, -1, sizeof(dp)); dp[0] = 0; for (int i = 0; i < n; i++) { for(int j = s; j >= 0; j --) { for(int x = 1; x <= nums[i][2]; x ++) { if(j - x * nums[i][1] < 0) break; if(dp[j - x * nums[i][1]] == -1) continue; if(dp[j] == -1) dp[j] =dp[j - x * nums[i][1]] + nums[i][0] * x; else dp[j] = max(dp[j], dp[j - x * nums[i][1]] + nums[i][0] * x ); } } } int ans = 0; for(int i = 0; i <= s; i ++) { ans = max(ans, dp[i]); } cout << ans << '\n'; return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */
#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...