Submission #876166

#TimeUsernameProblemLanguageResultExecution timeMemory
876166__Davit__Knapsack (NOI18_knapsack)C++17
37 / 100
1072 ms1368 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ff first #define ss second #define pb push_back #define vr(v) v.begin(),v.end() #define rv(v) v.rbegin(),v.rend() #define Code ios_base::sync_with_stdio(false); #define By cin.tie(NULL); #define Davit cout.tie(NULL); using namespace std; //#include "algo/debug.h" int main() { int S, n; cin >> S >> n; vector<int> V(n), W(n), K(n); for (int i = 0; i < n; i++) { cin >> V[i] >> W[i] >> K[i]; } vector<int> dp(S * n + 5, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < K[i]; j++) { for (int k = S * n; k >= 0; k--) { if (k - W[i] >= 0)dp[k] = max(dp[k], dp[k - W[i]] + V[i]); } } } int answer = 0; for (int k = S; k >= 0; k--) { answer = max(answer, dp[k]); } cout << answer << 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...