Submission #1254630

#TimeUsernameProblemLanguageResultExecution timeMemory
1254630mngoc._.Knapsack (NOI18_knapsack)C++20
100 / 100
204 ms3048 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int , int> const int N = 1e5 + 5; int n , s; vector<pii> adj[2005]; int dp[2005]; void solve(void){ cin >> s >> n; for(int i = 1 ; i <= n ; i++) { int c , w , k; cin >> c >> w >> k; adj[w].push_back({c , k}); } for(int i = 1 ; i <= s ; i++){ sort(adj[i].begin() , adj[i].end() , greater<pii>()); for(int j = s ; j >= 0; j--){ int cnt = 0 , sum = 0; for(int k = 0 ; k < adj[i].size(); k++){ for(int z = 0 ; z < adj[i][k].second ; z++){ cnt++; sum += adj[i][k].first; if(j < cnt * i) break; dp[j] = max(dp[j] , dp[j - cnt * i] + sum); } } } } int res = 0; for(int i = 0 ; i <= s; i++) res = max(res , dp[i]); cout << res; } signed main(void){ ios_base :: sync_with_stdio(false); cin.tie(NULL); solve(); 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...