Submission #1165460

#TimeUsernameProblemLanguageResultExecution timeMemory
1165460enzyKnapsack (NOI18_knapsack)C++20
73 / 100
344 ms327680 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int maxs=2e3+10; const int maxn=1e5+10; const int inf=1e18+10; int dp[maxs], v[maxn], w[maxn], k[maxn]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int s, n; cin >> s >> n; vector<pair<int,int>>process; for(int i=1;i<=n;i++){ cin >> v[i] >> w[i] >> k[i]; for(int q=1;q<=min(k[i],(s/w[i]));q++) process.push_back({w[i],v[i]}); } for(int i=0;i<process.size();i++){ pair<int,int>p=process[i]; for(int j=s;j>=0;j--){ if(p.first<=j) dp[j]=max(dp[j],dp[j-p.first]+p.second); } } int resp=0; for(int i=0;i<=s;i++) resp=max(resp,dp[i]); cout << resp << endl; 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...