제출 #1014803

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