Submission #1030504

#TimeUsernameProblemLanguageResultExecution timeMemory
1030504LmaoLmaoKnapsack (NOI18_knapsack)C++17
37 / 100
20 ms2940 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; using aa = array<int,3>; const int N = 1e6+5; const int INF = 1e9; ll dp[2005]; vector<ii> m[2005]; int pre[2005][2005]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,s; cin >> s >> n; for(int i=1;i<=s;i++) { dp[i]=0; } dp[0]=0; for(int i=1;i<=n;i++) { int v,w,k; cin >> v >> w >> k; m[w].push_back({v,k}); } for(int i=1;i<=s;i++) { sort(m[i].begin(),m[i].end(),greater<>()); } for(int i=1;i<=s;i++) { int cur=0; for(ii x:m[i]) { int t=cur; cur+=x.second*i; cur=min(cur,s); for(int j=t+i;j<=cur;j+=i) { pre[i][j]=pre[i][j-i]+x.first; } if(cur>=s) break; } } ll ans=0; for(int i=1;i<=s;i++) { for(ll j=s;j>0;j--) { for(int k=1;i*k<=j;k++) { dp[j]=max(dp[j],dp[j-i*k]+pre[i][i*k]); ans=max(ans,dp[j]); } } } cout << ans; 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...