제출 #597227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597227		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 prevW 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 prevW, wIndex, cnt;

    DP() {
        val = -1;
        prevW = -1;
    }
    DP(ll val, int prevW, int wIndex, int cnt) {
        this->val = val;
        this->prevW = prevW;
        this->wIndex = wIndex;
        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 -> prevW, e.f -> val, e.s -> cnt. Sorted in descending order
    map<int, vector<pair<int, int>>, greater<int>> items;
    FOR(n) {
        int val, prevW, cnt; cin >> val >> prevW >> cnt;
        if (prevW <= maxWeight) {
            items[prevW].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 (int basketW = 0;basketW <= maxWeight;basketW++) {
        if (dp[basketW].val == -1) {
            // skip since this state cannot be reached anyways
            continue;
        }

        // transition 
        for (auto& currItem : items) {
            int newWeight = basketW + currItem.f;
            if ((currItem.f > dp[basketW].prevW) || (newWeight > maxWeight)) {
                continue;
            }
            else if (currItem.f == dp[basketW].prevW) {
                if (dp[basketW].cnt < currItem.s[dp[basketW].wIndex].s) {
                    // more of this particular item can be added
                    ll newVal = dp[basketW].val + currItem.s[dp[basketW].wIndex].f;
                    if ((newVal > dp[newWeight].val) && (currItem.f > dp[newWeight].prevW)) {
                        dp[newWeight] = DP(newVal, currItem.f, dp[basketW].wIndex, dp[basketW].cnt + 1);
                    }
                }
                else if (dp[basketW].wIndex < currItem.s.size() - 1) {
                    // an item with the same prevW as the previous item can be
                    // added
                    ll newVal = dp[basketW].val + currItem.s[dp[basketW].wIndex + 1].f;
                    if ((newVal > dp[newWeight].val) && (currItem.f > dp[newWeight].prevW)) {
                        dp[newWeight] = DP(newVal, currItem.f, dp[basketW].wIndex + 1, 1);
                    }
                }
            }
            else {
                ll newVal = dp[basketW].val + currItem.s[0].f;
                if ((newVal > dp[newWeight].val) && (currItem.f > dp[newWeight].prevW)) {
                    dp[newWeight] = DP(newVal, currItem.f, 0, 1);
                }
            }
        }
    }

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

    cout << ans;

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

    //     // transition
    //     bool isStart = true;
    //     for (auto j = items.find(dp[i].prevW);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].wIndex].s) {
    //                 // all of this particular item is taken
    //                 if (dp[i].wIndex < j->s.size() - 1) {
    //                     // there are still items of this particular prevW left
    //                     ll newVal = dp[i].val + j->s[dp[i].wIndex + 1].f;
    //                     if (newVal > dp[newWeight].val && j->f >= dp[newWeight].prevW) {
    //                         dp[newWeight] = DP(newVal, j->f, dp[i].wIndex + 1, 1);
    //                     }
    //                 }
    //             }
    //             else {
    //                 ll newVal = dp[i].val + j->s[dp[i].wIndex].f;
    //                 if (newVal > dp[newWeight].val && j->f >= dp[newWeight].prevW) {
    //                     dp[newWeight] = DP(newVal, j->f, dp[i].wIndex, dp[i].cnt + 1);
    //                 }

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

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

    // cout << ans;

    return 0;
}

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:99:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 else if (dp[basketW].wIndex < currItem.s.size() - 1) {

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