Submission #1211696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211696		nayman_42	Knapsack (NOI18_knapsack)	C++20	12 / 100	1096 ms	432 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

bool check(map<int, map<int, int>>& dp, int n, int s)
{
    if (dp.find(n) != dp.end())
    {
        if (dp[n].find(s) != dp[n].end())
        return true;
        return false;
    }
    return false;
}

int answer(map<int, map<int, int>>& dp, vector<int>& value, vector<int>& weight, vector<int>& copies, int s, int n)
{
    if (copies[n] < 0 || s < 0)
    return -1e9;
    if(n < 0)
    return 0;
     if (n == 0)
    {
        int can_take = min(copies[n], s / weight[n]);
        return dp[n][s] = can_take * value[n];
    }
    
    int best = answer(dp, value, weight, copies, s, n - 1);  // Skip this item

    for (int k = 1; k <= copies[n]; ++k) {
        int total_weight = k * weight[n];
        int total_value = k * value[n];
        if (s >= total_weight) {
            best = max(best, answer(dp, value, weight, copies, s - total_weight, n - 1) + total_value);
        }
    }

    return dp[n][s] = best;
}

int main() {
    long long int s, n;
    cin >> s >> n;
    vector<int> value;
    vector<int> weight;
    vector<int> copies;
    int temp = n;
    while (n--)
    {
        int vi, wi, ki;
        cin >> vi >> wi >> ki;
        value.push_back(vi);
        weight.push_back(wi);
        copies.push_back(ki);
    }
    map<int, map<int, int>> dp;
    cout << answer(dp, value, weight, copies, s, temp - 1) << endl;
}

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