Submission #1205024

#TimeUsernameProblemLanguageResultExecution timeMemory
1205024andrejikusKnapsack (NOI18_knapsack)C++20
100 / 100
67 ms6752 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 = 4003; ll dp[N][2]; multiset<pair<ll, ll>, greater<>> pq[N]; void solve() { int s, n; cin >> s >> n; vector<tuple<ll, ll, ll>> items; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; pq[w].emplace(v, k); } int red = 0; for (int w = 1; w <= s; w++) { for (int k = s; k >= 0; k--) { dp[k][red] = dp[k][red^1]; ll ww = 0, sumv = 0; for (auto [v1, k1] : pq[w]) { if (k-(ww+w) < 0) break; for (int z = 0; z < k1 && k-(ww+w) >= 0; z++) { ww += w; sumv += v1; dp[k][red] = max(dp[k][red], dp[k-ww][red^1] + sumv); } } } 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...