Submission #1089508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089508		vjudge1	Knapsack (NOI18_knapsack)	C++14	73 / 100	1058 ms	25288 KiB

knapsack

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e6 + 5, mod = 1e9 + 7;
int n, m;
int dp[maxn];
vector<array<int, 2>> a;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        int val, w, num;
        cin >> val >> w >> num;
        num = min(num, m / w);
        int cur = 1;
        while (num >= cur)
        {
            a.push_back({val * cur, w * cur});
            num -= cur;
            cur *= 2;

        }
        if (num)
            a.push_back({val * num, w * num});
    }
    memset(dp, -0x3f, sizeof dp);
    int oo = dp[0];
    dp[0] = 0;
    for (auto p : a)
    {
        int u = p[0], v = p[1];
        for (int i = m; i >= v; i--) if (dp[i - v] != oo)
            dp[i] = max(dp[i], dp[i - v] + u);
    }

    cout << *max_element(dp, dp + m + 1);
}

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