Submission #1144907

#TimeUsernameProblemLanguageResultExecution timeMemory
1144907zhasynKnapsack (NOI18_knapsack)C++20
100 / 100
156 ms528 KiB
#include <bits/stdc++.h> #define pb push_back #define pf push_front using namespace std; #define F first #define S second typedef long long ll; #define pii pair <int, int> #define pll pair <ll, ll> typedef long double ld; const ll N = 2000 + 100, M = 4096 + 10, len = 21, inf = 1e18; const ll mod = 1e9 + 7; ll dp[N], val, ans; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int s, n, w, k; cin >> s >> n; for(int i = 0; i <= s; i++){ dp[i] = -1; } dp[0] = 0; for(int i = 0; i < n; i++){ cin >> val >> w >> k; while(k--){ bool was = false; for(int j = s; j >= w; j--){ if(dp[j - w] == -1) continue; if(dp[j - w] + val > dp[j]){ was = true; dp[j] = dp[j - w] + val; } } if(was ==false) break; } } for(int i = 0; i <= s;i++){ ans = max(ans, dp[i]); } cout << ans; 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...