Submission #552761

#	Time	Username	Problem	Language	Result	Execution time	Memory
552761		nhuang685	Knapsack (NOI18_knapsack)	C++17	12 / 100	34 ms	63064 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];
        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 - 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:19:18: warning: statement has no effect [-Wunused-value]
   19 | #define dbg(...) 0
      |                  ^
knapsack.cpp:76:5: note: in expansion of macro 'dbg'
   76 |     dbg(dp);
      |     ^~~

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