Submission #1140177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140177		hemaprakash	Knapsack (NOI18_knapsack)	C++20	49 / 100	3 ms	328 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s, n;
    cin >> s >> n;

    vector<long long> dp(s + 1);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        for (int j = s; j >= w; j--) {
                int lo = 1, hi = k;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    long long weight = 1LL * mid * w;
                    if (weight > j) {
                        hi = mid - 1;
                    } else {
                        long long price = 1LL * mid * v + dp[j - weight];
                        if (price >= dp[j]) {
                            dp[j] = price;
                            lo = mid + 1;
                        } else {
                            hi = mid - 1;
                        }
                    }
                }
        }
    }

    cout << dp[s] << "\n";

    return 0;
}

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