Submission #553798

#	Time	Username	Problem	Language	Result	Execution time	Memory
553798		thecodingwizard	Knapsack (NOI18_knapsack)	C++11	100 / 100	140 ms	67552 KiB

knapsack

#include <bits/stdc++.h>

#ifdef VSLOCAL
#include "debug/d.h"
#endif
#ifdef LOCAL
#include "../../debug/d.h"
#endif

using namespace std;

using ll = long long;
using ld = long double;

#if defined(LOCAL) || defined(VSLOCAL)
#define dbg(...) line_info(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 0
void nline() {}
#endif

struct item {
    ll W, V, K;
    bool operator< (const item that) const {
        return (W == that.W) ? V > that.V : W < that.W;
    }
};

ostream& operator<< (ostream& out, item i) {
    out << "{" << i.V << ", " << i.W << ", " << i.K << "}";
    return out;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("log.txt", "w", stderr);
    #endif

    int S, N;
    cin >> S >> N;

    vector<item> items (N);
    for (int i = 0; i < N; ++i) {
        cin >> items[i].V >> items[i].W >> items[i].K;
    }

    sort(items.begin(), items.end());
    dbg(items);

    vector<vector<ll>> value (S + 1, vector<ll> (S + 1));
    vector<vector<ll>> dp (S + 1, vector<ll> (S + 1)); // maximum value

    int index = 0;
    for (int i = 1; i <= S; ++i) {
        int count = 0;
        dp[i] = dp[i - 1];
        while (index < items.size() && items[index].W < i) index++;
        if (index >= items.size() || items[index].W > i) continue;
        for (int j = i; j <= S; j += i) {
            count++;
            if (count > items[index].K) {
                count = 1;
                index++;
            }
            if (index >= N || items[index].W != i) break;
            value[i][j] = value[i][j - i] + items[index].V;

            for (int k = j; k <= S; ++k) {
                // dp[i][k] = max(dp[i][k], dp[i - 1][k]);
                dp[i][k] = max(dp[i][k], dp[i][k - 1]);
                dp[i][k] = max(dp[i][k], dp[i - 1][k - j] + value[i][j]);
            }
        }
    }
    dbg(dp);
    cout << dp[S][S] << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 | #define dbg(...) 0
      |                  ^
knapsack.cpp:52:5: note: in expansion of macro 'dbg'
   52 |     dbg(items);
      |     ^~~
knapsack.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while (index < items.size() && items[index].W < i) index++;
      |                ~~~~~~^~~~~~~~~~~~~~
knapsack.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (index >= items.size() || items[index].W > i) continue;
      |             ~~~~~~^~~~~~~~~~~~~~~
knapsack.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 | #define dbg(...) 0
      |                  ^
knapsack.cpp:79:5: note: in expansion of macro 'dbg'
   79 |     dbg(dp);
      |     ^~~

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