Submission #1247861

#TimeUsernameProblemLanguageResultExecution timeMemory
1247861deeperxdKnapsack (NOI18_knapsack)C++20
73 / 100
1093 ms428 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 998244353 #define SIZE 2001 ll dp[SIZE]{0}; int main(){ int s, n; cin >> s >> n; for(int i = 0 ; i < SIZE; i++) dp[i] = -1; dp[0] = 0; for(int i = 0; i < n; i++){ int v, w, k; cin >> v >> w >> k; for(int j = 0; j < min(s, k); j++){ for(int c = s-w; c >= 0; c--){ if (dp[c] == -1) continue; if (dp[c+w] == -1) dp[c+w] = dp[c] + v; else dp[c+w] = max(dp[c+w], dp[c]+v); } } } ll mx = 0; for(int i = 0; i <= s; i++){ if (dp[i] == -1)continue; mx = max(mx, dp[i]); } cout << mx << 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...