Submission #674086

#TimeUsernameProblemLanguageResultExecution timeMemory
674086RadicaIKnapsack (NOI18_knapsack)C++17
100 / 100
188 ms19324 KiB
#include <bits/stdc++.h> #define pi pair<int, int> #define x first #define y second #define pb push_back #define mp make_pair using namespace std; int main(){ int s, n; cin >> s>>n; vector<pi> stuff[s+1]; int dp[s+1][s+1]; for(int i=0; i<=s; i++)for(int j=0; j<=s; j++) dp[i][j] =0; for(int i=0; i<n; i++){ int a,b,c; cin >> a>>b>>c; if(b>s) continue; stuff[b].pb(mp(a,c)); } for(int i=0; i<=s; i++) sort(stuff[i].begin(), stuff[i].end()); int ever = 0; for(int i=1; i<=s; i++)for(int j=1; j<=s; j++){ dp[i][j] = dp[i][j-1]; int sum = 0, val = 0; for(int p = stuff[j].size()-1; p>=0; p-- ){ pi elem = stuff[j][p]; for(int t=1; t<=elem.y; t++){ sum += j; val += elem.x; if(sum > i) break; dp[i][j] = max(dp[i][j], dp[i-sum][j-1] + val); ever =max(ever, dp[i][j]); } if(sum > i) break; } } cout << ever; }
#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...