Submission #1204957

#TimeUsernameProblemLanguageResultExecution timeMemory
1204957andrejikusKnapsack (NOI18_knapsack)C++20
73 / 100
454 ms327680 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); } #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) const int N = 2003; int dp[N][2]; void solve() { int s, n; cin >> s >> n; vector<pair<int, int>> items; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; k = min(k, 2000); for (int j = 0; j < k; j++) items.push_back({v, w}); } int red = 0; for (auto [v, w] : items) { for (int j = s; j >= 0; j--) { dp[j][red] = dp[j][red^1]; if (j-w >= 0) dp[j][red] = max(dp[j][red], dp[j-w][red^1] + v); } red ^= 1; } cout << dp[s][red^1] << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t=1; //cin >> t; while (t--) { solve(); } }
#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...