Submission #597179

#	Time	Username	Problem	Language	Result	Execution time	Memory
597179		jayser6	Knapsack (NOI18_knapsack)	C++14	12 / 100	1 ms	340 KiB

knapsack

/*____________________________________________________________
// started : 07/13/22
// finished:
// problem : https://oj.uz/problem/view/NOI18_knapsack and file:///C:/Users/jayse/Downloads/statement_en.pdf
____________________________________________________________*/

#include <bits/stdc++.h>

#define FOR(n) for (int i = 0;i < n;i++)
#define FORO(n) for (int i = 1;i < n;i++)
#define ROF(n) for (int i = n - 1;i >= 0;i--)
#define ROFO(n) for (int i = n - 1;i >= 1;i--)
#define loop while (true) // rust woooo
#define ALL(arr) arr.begin(), arr.end()
#define lower lower_bound 
#define upper upper_bound
#define ll long long
#define uint unsigned int
#define hashmap unordered_map
#define hashset unordered_set
#define p_queue priority_queue
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define endl "\n"
#define BIG_NUMBER 1e18
#define BIG_PRIME 999998727899999 // this number has 15 digits
#define PRIME32 1e9 + 7 
#define ASCII_PRIME 257
#define ALPHA_PRIME 29

using namespace std;

struct DP {
    ll val;

    // the weight of the previous item that we landed on the dp state with, the
    // index of the item in the vector, the number of specific items already
    // bought
    int weight, wI, cnt;

    DP() {
        val = -1;
    }
    DP(ll val, int weight, int wI, int cnt) {
        this->val = val;
        this->weight = weight;
        this->wI = wI;
        this->cnt = cnt;
    }
};

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

    // maxWeight is S from the problem statement, can't use s as variable name
    // because macro though
    int maxWeight, n; cin >> maxWeight >> n;

    // key -> weight, e.f -> val, e.s -> cnt. Sorted in descending order
    map<int, vector<pair<int, int>>, greater<int>> items;
    FOR(n) {
        int val, weight, cnt; cin >> val >> weight >> cnt;
        if (weight <= maxWeight) {
            items[weight].pb({ val, cnt });
        }
    }

    vector<DP> dp(maxWeight + 1);
    for (auto& curr : items) {
        sort(ALL(curr.s), greater<pair<int, int>>());
        dp[curr.f] = DP(curr.s[0].f, curr.f, 0, 1);
    }

    FOR(maxWeight + 1) {
        if (dp[i].val == -1) {
            continue;
        }

        // transition
        bool isStart = true;
        for (auto j = items.find(dp[i].weight);j != items.end();j++) {
            int newWeight = i + j->f;
            if (newWeight > maxWeight) {
                // can't add this item, try a lighter item
                isStart = false;
                continue;
            }

            if (isStart) {
                isStart = false;

                if (dp[i].cnt == j->s[dp[i].wI].s) {
                    // all of this particular item is taken
                    if (dp[i].wI < j->s.size() - 1) {
                        // there are still items of this particular weight left
                        ll newVal = dp[i].val + j->s[dp[i].wI + 1].f;
                        if (newVal > dp[newWeight].val && j->f >= dp[newWeight].weight) {
                            dp[newWeight] = DP(newVal, j->f, dp[i].wI + 1, 1);
                        }
                    }
                }
                else {
                    ll newVal = dp[i].val + j->s[dp[i].wI].f;
                    if (newVal > dp[newWeight].val && j->f >= dp[newWeight].weight) {
                        dp[newWeight] = DP(newVal, j->f, dp[i].wI, dp[i].cnt + 1);
                    }

                }
            }
            else {
                ll newVal = dp[i].val + j->s[0].f;
                if (newVal > dp[newWeight].val && j->f >= dp[newWeight].weight) {
                    dp[newWeight] = DP(newVal, j->f, 0, 1);
                }
            }
        }
    }

    ll ans = 0;
    FOR(maxWeight + 1) {
        ans = max(ans, dp[i].val);
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:98:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                     if (dp[i].wI < j->s.size() - 1) {

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