제출 #401726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401726		Senapati23	Knapsack (NOI18_knapsack)	C++14	17 / 100	5 ms	4172 KiB

knapsack

#include <bits/stdc++.h>
//#define int long long int
#define mod 1000000007
#define inf (1LL << 60)
#define endl "\n"
//#define N 1e6 + 1
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define all(x) begin(x), end(x)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define prec cout << fixed << setprecision(9);
using namespace std;
// Debugging starts
#define dbg(...)                          \
    cout << "[" << #__VA_ARGS__ << "]: "; \
    cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N>
int SIZE(const T (&t)[N])
{
    return N;
}
template <typename T>
int SIZE(const T &t)
{
    return t.size();
}
string to_string(const string s, int x1 = 0, int x2 = 1e9)
{
    return '"' + ((x1 < s.size()) ? s.substr(x1, x2 - x1 + 1) : "") + '"';
}
string to_string(const char *s) { return to_string((string)s); }
string to_string(const bool b) { return (b ? "true" : "false"); }
string to_string(const char c) { return string({c}); }
template <size_t N>
string to_string(const bitset<N> &b, int x1 = 0, int x2 = 1e9)
{
    string t = "";
    for (int __iii__ = min(x1, SIZE(b)), __jjj__ = min(x2, SIZE(b) - 1);
            __iii__ <= __jjj__; ++__iii__)
    {
        t += b[__iii__] + '0';
    }
    return '"' + t + '"';
}
template <typename A, typename... C>
string to_string(const A(&v), int x1 = 0, int x2 = 1e9, C... coords);
int l_v_l_v_l = 0, t_a_b_s = 0;
template <typename A, typename B>
string to_string(const pair<A, B> &p)
{
    l_v_l_v_l++;
    string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
    l_v_l_v_l--;
    return res;
}
template <typename A, typename... C>
string to_string(const A(&v), int x1, int x2, C... coords)
{
    int rnk = rank<A>::value;
    string tab(t_a_b_s, ' ');
    string res = "";
    bool first = true;
    if (l_v_l_v_l == 0)
        res += endl;
    res += tab + "[";
    x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v));
    auto l = begin(v);
    advance(l, x1);
    auto r = l;
    advance(r, (x2 - x1) + (x2 < SIZE(v)));
    for (auto e = l; e != r; e = next(e))
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        l_v_l_v_l++;
        if (e != l)
        {
            if (rnk > 1)
            {
                res += endl;
                t_a_b_s = l_v_l_v_l;
            };
        }
        else
        {
            t_a_b_s = 0;
        }
        res += to_string(*e, coords...);
        l_v_l_v_l--;
    }
    res += "]";
    if (l_v_l_v_l == 0)
        res += endl;
    return res;
}
void dbgm() { ; }
template <typename Heads, typename... Tails>
void dbgm(Heads H, Tails... T)
{
    cout << to_string(H) << " | ";
    dbgm(T...);
}
#define dbgm(...)                         \
    cout << "[" << #__VA_ARGS__ << "]: "; \
    dbgm(__VA_ARGS__);                    \
    cout << endl
// debugging ends

//Read Templates Starts
template <typename T = int>
std::vector<std::vector<T>> ReadMatrix(int row_count = 0, int column_count = 0,
                                       std::istream &in_stream = std::cin);
template <typename T = int>
std::vector<T> ReadArray(int size = 0, std::istream &in_stream = std::cin);
//Read Templates Ends
//Solve f(x) starts

void solve()
{
    int knapsack, n, w;
    cin >> knapsack >> n;
    vector<int> values(n), weights(n);
    for (int i = 0; i < n; i++)
    {
        cin >> values[i] >> weights[i] >> w;
        int initialSum = 1, p = 2;
        while (p < w)
        {
            if (initialSum + p <= knapsack)
            {
                initialSum += p;
                weights.push_back(p * weights[i]);
                values.push_back(p * values[i]);
            }
            p *= 2;
        }
        if (w - initialSum != 0)
        {
            weights.push_back((knapsack - initialSum) * weights[i]);
            values.push_back((knapsack - initialSum) * values[i]);
        }
    }

    // dbg(weights);
    // dbg(values);

    //Recalculating n after adding new weights

    n = weights.size();

    vector<vector<int>> dp(n + 1, vector<int>(knapsack + 1, 0));
    dp[0][0] = 0;
    int finalAns = INT_MIN;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= knapsack; j++)
        {

            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1])
            {
                dp[i][j] = max(dp[i - 1][j - weights[i - 1]] + values[i - 1], dp[i][j]);
            }
            finalAns =  finalAns = max(dp[i][j], finalAns);
        }
    }
    // dbg(dp);

    cout << finalAns << endl;
}
//Init Code
void init_code()
{
    fast_io;
    // freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);
}
int32_t main()
{
    init_code();
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
//Init Code Ends

template <typename T>
std::vector<T> ReadArray(int size, std::istream &in_stream)
{
    if (!size)
    {
        in_stream >> size;
    }
    std::vector<T> array(size);
    for (auto &element : array)
    {
        in_stream >> element;
    }
    return array;
}
template <typename T>
std::vector<std::vector<T>> ReadMatrix(int row_count, int column_count, std::istream &in_stream)
{
    if (!row_count)
    {
        in_stream >> row_count >> column_count;
    }
    else if (!column_count)
    {
        column_count = row_count;
    }

    std::vector<std::vector<T>> matrix(row_count, std::vector<int>(column_count));
    for (auto &row : matrix)
    {
        for (auto &entry : row)
        {
            in_stream >> entry;
        }
    }

    return matrix;
}

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'std::string to_string(std::string, int, int)':
knapsack.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     return '"' + ((x1 < s.size()) ? s.substr(x1, x2 - x1 + 1) : "") + '"';
      |                    ~~~^~~~~~~~~~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:170:22: warning: operation on 'finalAns' may be undefined [-Wsequence-point]
  170 |             finalAns =  finalAns = max(dp[i][j], finalAns);
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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