제출 #791254

#제출 시각아이디문제언어결과실행 시간메모리
791254gustavo_dKnapsack (NOI18_knapsack)C++17
12 / 100
111 ms262144 KiB
// https://oj.uz/problem/view/NOI18_knapsack > p83 #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int S, n; cin >> S >> n; vector<int> v(n); vector<int> w(n); vector<int> K(n); for (int i=0; i<n; i++) cin >> v[i] >> w[i] >> K[i]; for (int i=0; i<n; i++) { K[i] = min(K[i], (S/w[i])+min(S%w[i], 1)); } K.push_back(0); vector<vector<vector<int>>> dp(n+1, vector<vector<int>> (S+1, vector<int> (S+1, 0))); for (int i=n-1; i>=0; i--) { for (int P=0; P<=S; P++) { for (int k=0; k<=S; k++) { if (k>0 and P>=w[i]) { dp[i][P][k] = dp[i][P-w[i]][k-1] + v[i]; } dp[i][P][k] = max( dp[i][P][k], dp[i+1][P][K[i+1]] ); } } } cout << dp[0][S][K[0]] << endl; 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...