Submission #1248112

#TimeUsernameProblemLanguageResultExecution timeMemory
1248112one_unknownKnapsack (NOI18_knapsack)C++20
37 / 100
1096 ms1864 KiB
#include <bits/stdc++.h> using namespace std; #define int long long using vi = vector<int>; using vpii = vector<pair<int,int>>; #define MOD 1000000007 #define all(arr) arr.begin(), arr.end() #define take(arr) for(auto &x : arr) cin >> x; #define print(arr) for(auto &x : arr) cout << x << " "; cout << "\n"; #define out(val) cout<<((val == 1) ? "YES" : "NO")<<endl; void solve() { int n,x; cin>>x>>n; vector<vector<int>> arr(n, vector<int>(3, 0)); for(int i = 0; i<n; ++i){ cin>>arr[i][0]>>arr[i][1]>>arr[i][2]; } vector<vector<int>> dp(n+1, vector<int>(x+1, 0)); for(int i = 1; i<=n; ++i){ for(int j = 0; j<=x; ++j){ int time = arr[i - 1][2]; for(int k = 0; k<=time; ++k){ if(j >= k*arr[i-1][1]){ dp[i][j] = max(dp[i][j], dp[i-1][j - k*arr[i-1][1]] + k*arr[i-1][0]); } } } } cout<<dp[n][x]<<endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; 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...