Submission #744400

#TimeUsernameProblemLanguageResultExecution timeMemory
744400Azm1tKnapsack (NOI18_knapsack)C++17
37 / 100
5 ms6356 KiB
#include "bits/stdc++.h" using namespace std; #define forn for (int i = 0; i < n; i++) // #define int long long #define ed "\n" #define cyes cout << "YES\n" #define cno cout << "NO\n" #define pb push_back #define deb cout << "Hi\n" #define pint pair<int, int> const long long MOD = 1000000007; void dbg_out(){cerr<<"\n";} template<typename Head,typename... Tail> void dbg_out(Head H,Tail... T){cerr<<' '<<H;dbg_out(T...);} #define debug(...) cerr<<"("<<#__VA_ARGS__<<"):",dbg_out(__VA_ARGS__) //-------------------------------------------------------------------------------------------------------------------------------------------------------------------// int32_t main(){ std::ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int w, n; cin>>w>>n; vector<array<int, 3>> v(n); forn cin>>v[i][0]>>v[i][1]>>v[i][2]; vector<pair<int, long long>> v2; for(auto val: v){ int vi = val[0]; int wi = val[1]; int ki = val[2]; for(int i = 0; i <= 34; i++){ if(ki >= (1LL << i)){ long long tt = (1LL << i); long long cost = tt*vi; v2.pb({tt*wi, cost}); ki -= tt; } } long long cost = ki*vi; if(ki > 0) v2.pb({ki*wi, cost}); } // for(auto val: v2) debug(val.first, val.second); n = v2.size(); vector<vector<long long>> dp(n, vector<long long> (w+1, 0)); for(int i = 0; i < n; i++){ for(int j = 1; j <= w; j++){ if(i == 0){ if(j >= v2[i].first) dp[i][j] = v2[i].second; } else{ dp[i][j] = dp[i-1][j]; if(j-v2[i].first >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-v2[i].first] + v2[i].second); } } } cout << dp[n-1][w] << ed; }
#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...