Submission #1265798

#TimeUsernameProblemLanguageResultExecution timeMemory
1265798sathegoodkidKnapsack (NOI18_knapsack)C++20
73 / 100
1093 ms2380 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long ll MOD = 1e9 +7; int MAX_C = 1e8+1; int main(){ int s,n; cin >> s >> n; vector <int> w(n); vector <ll> v(n); vector <ll> k(n); for(int i = 0 ; i < n ;i++){ cin >> v[i] >> w[i] >> k[i]; } vector <ll> dp(s+1,0); for(int i = 0 ; i < n ; i++){ for(int j = s; j >= w[i] ; j--){ int u = j/w[i]; if(k[i] < u){ u = k[i]; } for(int a = 1; a <= u ;a++){ dp[j] = max(dp[j],dp[j - a*w[i]] + a*v[i]); } } } cout << dp[s] << endl; }
#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...