제출 #1143630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143630		xnscdev	Knapsack (NOI18_knapsack)	C++20	17 / 100	62 ms	33336 KiB

knapsack

// 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

struct Comp
{
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) const
    {
        if (a.first == b.first)
            return a.second > b.second;
        return a.first < b.first;
    }
};

void solve()
{
#ifdef DEBUG
    cout << "\033[31;1m======================================================================\033[0m" << endl;
#endif
    int s, n;
    cin >> s >> n;
    vector<vector<pair<int, int>>> x(s + 1);
    for (int i = 0; i < n; i++)
    {
        int v, w, k;
        cin >> v >> w >> k;
        for (int j = 0; j < k; j++)
            x[w].emplace_back(v, k);
    }
    vector<ll> dp(s + 1);
    for (int i = 1; i <= s; i++)
    {
        ranges::sort(x[i], greater());
        int proc = s / i;
        int curr = 0;
        while (proc > 0 && curr < x[i].size())
        {
            int amt = min(proc, x[i][curr].second);
            proc -= amt;
            x[i][curr].second -= amt;
            for (int j = s; j >= i; j--)
                dp[j] = max(dp[j], dp[j - i] + x[i][curr].first);
            if (x[i][curr].second == 0)
                curr++;
        }
    }
    cout << *ranges::max_element(dp) << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27