Submission #1202969

#TimeUsernameProblemLanguageResultExecution timeMemory
1202969jahongirKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms328 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define pi pair<int,int> #define vi vector<int> #define pb push_back #define all(a) a.begin(),a.end() void solve(){ int s,n; cin >> s >> n; vector<ll> dp(s+1,0); while(n--){ int v,w,k; cin >> v >> w >> k; k = min(k,s/w); int cur = 1; while(true){ k-=cur; for(int i = s; i >= cur*w; i--) dp[i] = max(dp[i],dp[i-cur*w] + 1ll*cur*v); cur <<= 1; if(k < cur) break; } if(k){ for(int i = s; i >= k*w; i--) dp[i] = max(dp[i],dp[i-k*w] + 1ll*k*v); } for(int i = 1; i <= s; i++) dp[i] = max(dp[i],dp[i-1]); } cout << *max_element(all(dp)); } signed main(){ // freopen("snowcow.in","r",stdin); // freopen("snowcow.out","w",stdout); cin.tie(0)->sync_with_stdio(0); int t = 1; while(t--) solve(); }
#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...