Submission #1089523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089523		vjudge1	Knapsack (NOI18_knapsack)	C++14	100 / 100	180 ms	9176 KiB

knapsack

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

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

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;
        b[w].emplace_back(val, num);
    }
    for (int i = 1; i <= m; i++)
    {
        int lim = m;
        sort(b[i].begin(), b[i].end(), greater<>());
        for (auto p : b[i])
        {
            int val, num;
            tie(val, num) = p;
            num = min(num, lim / i);
            int cur = 1;
            while (num >= cur)
            {
                a.push_back({val * cur, i * cur});
                num -= cur;
                lim -= cur;
                cur *= 2;
            }
            if (num)
                a.push_back({val * num, i * num}),
                lim -= 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: 27 / 27