제출 #1014820

#제출 시각아이디문제언어결과실행 시간메모리
1014820KindaGoodGamesKnapsack (NOI18_knapsack)C++14
29 / 100
1 ms456 KiB
#include <bits/stdc++.h> #define ll long long //#define int ll #define pii pair<int, int> #define tiii tuple<int, int, int> using namespace std; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, s; cin >> s >> n; vector<int> value(n), weight(n), capacity(n); vector<int> dp(s+1); for (int i = 0; i < n; i++) { cin >> value[i] >> weight[i] >> capacity[i]; } if(n == 1){ cout << min(s/weight[0], capacity[0]) * value[0]; return 0; } for (int i = 0; i < n; i++) { int la = capacity[i]; for (int j = s; j > 0; j--) { //dp[j] = max(dp[j],dp[j - 1]); if (j < weight[i]) continue; for (int k = la; k > 0; k--) { if(j-(k*weight[i]) < 0){ la = k; break;} if(dp[j] <dp[j - (k*weight[i])] + (k*value[i])){ dp[j] = dp[j - (k*weight[i])] + (k*value[i]); break; } } } } int ma = 0; for(int i = 0; i <= s; i++){ ma = max(ma, dp[i]); } cout << ma; }
#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...