Submission #1198687

#TimeUsernameProblemLanguageResultExecution timeMemory
1198687mehraliiKnapsack (NOI18_knapsack)C++20
49 / 100
145 ms327680 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 indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define pb push_back #define pf push_front #define eb emplace_back #define ins insert #define F first #define S second #define MAXN 100005 #define LOG (int)log2(MAXN)+1 const int INF = 1e18; const int MOD = 998244353; const double EPS = 1e-8; int N, S; void slv(){ vector<pair<int, int>> a; for(int i = 0; i < N; i++){ int p, w, k; cin >> p >> w >> k; for(int i = 0; i < k; i++) a.pb({p, w}); } vector<vector<int>> dp(a.size()+1, vector<int>(S+1)); for(int i = 1; i <= a.size(); i++){ for(int j = 1; j <= S; j++){ dp[i][j] = dp[i-1][j]; if(j>=a[i-1].S) dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1].S]+a[i-1].F); } } cout << dp[a.size()][S] << '\n'; } void solve(){ cin >> S >> N; if(N!=1){ slv(); return; } int p, w, k; cin >> p >> w >> k; cout << min(S/w, k)*p << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while(t--) 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...