Submission #1204976

#TimeUsernameProblemLanguageResultExecution timeMemory
1204976andrejikusKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms3712 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; ll dp[N][2]; multiset<ll> dp2[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; items.push_back({v, w, k}); } int red = 0; for (auto [v, w, k] : items) { for (int j = 0; j <= s; j++) { dp[j][red] = dp[j][red^1]; if (dp2[j%w].empty()) { dp2[j%w].insert(dp[j][red^1] - (j/w)*v); continue; } if (dp2[j%w].size() > k) { int t = j-(k+1)*w; dp2[j%w].erase(dp2[j%w].find(dp[t][red^1] - (t/w)*v)); } auto kk = *dp2[j%w].rbegin() + (j/w)*v; dp2[j%w].insert(dp[j][red^1] - (j/w)*v); dp[j][red] = max(dp[j][red], kk); } for (int j = 0; j <= w; j++) dp2[j].clear(); 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...