Submission #957298

#	Time	Username	Problem	Language	Result	Execution time	Memory
957298		ifateen	Knapsack (NOI18_knapsack)	C++17	73 / 100	1057 ms	1484 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXS = 2005;
int dp[MAXS];
void add(int weight, int value) {
    for (int i = MAXS - 1; i >= 0; --i) {
        if (i + weight < MAXS) dp[i + weight] = max(dp[i + weight], value + dp[i]);
    }
}
signed main() {
    for (auto& i : dp) i = -1e18;
    dp[0] = 0;
    int n, s; cin >> s >> n;
    for (int i = 1; i <= n; ++i) {
        int value, weight, count;
        cin >> value >> weight >> count;
        count = min(count, s);
        int x = 1;
        while (count >= x) {
            add(weight * x, value * x);
            count -= x;
            x *= 2;
        }
        if (count) add(weight * count, value * count);
    }
    cout << *max_element(dp, dp + s + 1);
}

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