Submission #1165463

#TimeUsernameProblemLanguageResultExecution timeMemory
1165463enzyKnapsack (NOI18_knapsack)C++20
12 / 100
0 ms328 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]; bool cmp(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){ if(a.second.first*b.second.second>a.second.second*b.second.first) return true; return false; } 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; vector<pair<int,pair<int,int>>>order; for(int i=1;i<=n;i++){ cin >> v[i] >> w[i] >> k[i]; order.push_back({i,{v[i],w[i]}}); //for(int q=1;q<=min(k[i],(s/w[i]));q++) process.push_back({w[i],v[i]}); } sort(order.begin(),order.end(),cmp); reverse(order.begin(),order.end()); int at=s; for(auto p : order){ int i=p.first; for(int q=1;q<=min(k[i],(at/w[i]));q++) process.push_back({w[i],v[i]}); if(k[i]*w[i]>=at) at%=w[i]; else at-=k[i]*w[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...