Submission #1172330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172330		dbekarys	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 1e4 + 7;
const long long inf = 1e18;

// dp array to store the maximum value for a given weight
int dp[10000 + 7];

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

    int m, n;
    cin >> m >> n; // Maximum weight and number of items

    vector<pair<int, int>> items; // Vector to store {value, weight} pairs

    for (int i = 1; i <= n; i++) {
        int b, a, c;
        cin >> b >> a >> c; // Value, Weight, Count
        for (int k = 1; k <= c; k *= 2) {
            items.push_back({a * k, b * k});
            c -= k;
        }
        if (c > 0) {
            items.push_back({a * c, b * c});
        }
    }

    fill(dp, dp + 10000 + 1, inf); // Fill dp array with infinity
    dp[0] = 0;

    for (auto &[value, weight] : items) {
        for (int j = 10000; j >= weight; j--) {
            dp[j] = min(dp[j], dp[j - weight] + value);
        }
    }

    for (int i = 10000; i >= 0; i--) {
        if (dp[i] <= m) {
            cout << i;
            break;
        }
    }
}

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