Submission #1143643

#TimeUsernameProblemLanguageResultExecution timeMemory
1143643xnscdevKnapsack (NOI18_knapsack)C++20
100 / 100
66 ms33096 KiB
// https://oj.uz/problem/view/NOI18_knapsack #ifndef DEBUG #pragma GCC optimize("O3,unroll-loops") #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/trie_policy.hpp> #if defined(DEBUG) && defined(DEBUG_UTIL) #include "dsa_util.h" #endif // clang-format off using namespace std; using namespace __gnu_pbds; using ll = long long; using ull = unsigned long long; constexpr int INF = 0x3f3f3f3f; constexpr ll INFL = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-9; constexpr int dx[4] = {1, -1, 0, 0}; constexpr int dy[4] = {0, 0, 1, -1}; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); bool inside(int x, int y, int n, int m) { return x >= 0 && x < n && y >= 0 && y < m; } template <typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<>>; template <typename T, typename Comp = less<>> using ordered_set = tree<T, null_type, Comp, rb_tree_tag, tree_order_statistics_node_update>; using pref_trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>; template <typename, typename = void> struct is_iterable : false_type {}; template <typename T> struct is_iterable<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> : true_type {}; template <> struct is_iterable<string> : false_type {}; template <typename T> constexpr bool is_iterable_v = is_iterable<T>::value; template <typename T, typename V = enable_if_t<is_iterable_v<T>, typename T::value_type>> ostream &operator<<(ostream &os, const T &t) { for (const V &v : t) os << v << ' '; return os; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << '(' << p.first << ' ' << p.second << ')'; } void dbg_header_(const char *f, int l, const char *e) { cout << "\033[35m(" << f << ':' << l << ") \033[1m" << e << ":\033[0m "; } template <typename T, typename = enable_if_t<!is_iterable_v<T>>> void dbg_(const T &t, const char *f, int l, const char *e) { dbg_header_(f, l, e); cout << "\033[33;1m" << t << "\033[0m" << endl; } template <typename T, typename V = enable_if_t<is_iterable_v<T> && !is_iterable_v<typename T::value_type>, typename T::value_type>, typename = void> void dbg_(const T &t, const char *f, int l, const char *e) { dbg_header_(f, l, e); cout << "\033[33;1m"; for (const V &v : t) cout << v << ' '; cout << "\033[0m" << endl; } template <typename T, typename = enable_if_t<is_iterable_v<T> && is_iterable_v<typename T::value_type>, typename T::value_type>, typename = void, typename = void> void dbg_(const T &t, const char *f, int l, const char *e) { dbg_header_(f, l, e); cout << '\n'; for (int i = 0; i < t.size(); i++) cout << "\033[36m" << i << ":\033[33;1m " << t[i] << "\033[0m" << endl; } #ifdef DEBUG #define dbg(t) dbg_((t), __func__, __LINE__, #t) #else #define dbg(t) #endif // clang-format on void solve() { #ifdef DEBUG cout << "\033[31;1m======================================================================\033[0m" << endl; #endif int s, n; cin >> s >> n; map<int, vector<pair<int, int>>> m; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; m[w].emplace_back(v, k); } vector dp(m.size() + 1, vector<ll>(s + 1, -INFL)); dp[0][0] = 0; int a = 1; for (auto &[w, x] : m) { ranges::sort(x, greater()); for (int i = 0; i <= s; i++) { dp[a][i] = dp[a - 1][i]; int curr = 0; int used = 0; int c = 0; ll score = 0; while ((c + 1) * w <= i && curr < x.size()) { c++; score += x[curr].first; if (dp[a - 1][i - c * w] != -INFL) dp[a][i] = max(dp[a][i], dp[a - 1][i - c * w] + score); if (++used == x[curr].second) { used = 0; curr++; } } } a++; } cout << *ranges::max_element(dp.back()) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); 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...