Submission #1156729

#TimeUsernameProblemLanguageResultExecution timeMemory
115672921075028Knapsack (NOI18_knapsack)C++20
100 / 100
189 ms17680 KiB
#include<bits/stdc++.h> using namespace std; int dp[2001][2001]; unordered_map<int,vector<pair<int,int>>> m; long long func(int i,int s){ if(i==2001) return 0; if(dp[i][s]!=-1)return dp[i][s]; long long ans=0; long long val=0; int chk=0; ans=func(i+1,s); int cnt=1; for(auto p:m[i]){ for(int j=1;j<=p.second;j++){ if(cnt*i<=s){ val+=p.first; ans=max(ans,val+func(i+1,s-cnt*i)); cnt++; } else { chk=1; break; } } if(chk) break; } return dp[i][s]=ans; } int main(){ int s,n; cin>>s>>n; for(int i=0;i<=2000;i++){ for(int j=0;j<=2000;j++){ dp[i][j]=-1; } } for(int i=0;i<n;i++){ int v,w,k; cin>>v>>w>>k; m[w].push_back({v,k}); } for(int i=1;i<=2000;i++){{ sort(m[i].rbegin(),m[i].rend()); }} cout<<func(1,s)<<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...