Submission #401709

#	Time	Username	Problem	Language	Result	Execution time	Memory
401709		Senapati23	Knapsack (NOI18_knapsack)	C++14	17 / 100	2 ms	332 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 + 1), weights(n + 1);
    for (int i = 1; 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, INT_MIN));

    //dp[0][0] = 0;
    int dp[knapsack + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = knapsack; j >= 0; j--) {
            dp[j] = (weights[i] > j) ? dp[j] : max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    cout << dp[knapsack];

    // 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])
    //         {
    //             if (dp[i - 1][j - weights[i - 1]] != INT_MIN)
    //             {
    //                 dp[i][j] = max(dp[i - 1][j - weights[i - 1]] + values[i - 1], dp[i][j]);
    //             }
    //         }
    //     }
    // }
    // // dbg(dp);
    // int finalAns = INT_MIN;
    // for (int i = 0; i <= knapsack; i++)
    // {
    //     finalAns = max(dp[n][i], finalAns);
    // }
    // 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;
}

Compilation message (stderr)

knapsack.cpp: In function 'std::string to_string(std::string, long long int, long long int)':
knapsack.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long 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) : "") + '"';
      |                    ~~~^~~~~~~~~~

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