Submission #934979

#TimeUsernameProblemLanguageResultExecution timeMemory
934979shinigami_09Knapsack (NOI18_knapsack)C++17
12 / 100
1051 ms356 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int f(int n, int s, vector<int> &val, vector<int> &w, vector<int> &freq) { if(s==0)return 0; if(n<0)return 0; int ans = 0; if(w[n]<=s and freq[n]>0){ freq[n]--; ans = max( ans , val[n]+f(n,s-w[n],val,w,freq)); freq[n]++; ans = max( ans , f(n-1,s,val,w,freq)); } else{ ans = max( ans , f(n-1,s,val,w,freq)); } return ans; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int s, n; cin >> s >> n; vector<int> val(n), w(n), freq(n); for (int i = 0; i < n; i++) { cin >> val[i] >> w[i] >> freq[i]; } cout<< f(n-1,s,val,w,freq); 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...